verify/scc_dag.test.cpp

View this file on GitHub
Last update: 2020-02-25 06:59:12+09:00
Problem: http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=3075

Depends on

Code

#define PROBLEM "http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=3075"
#include "bits/stdc++.h"

using namespace std;
using i64 = long long;

const i64 MOD = 1e9 + 7;

#include "../lib/functions/scc.cpp"
#include "../lib/functions/scc_dag.cpp"


template <typename T>
bool chmax(T& x, T y){
    if(x < y){
        x = y;
        return true;
    }
    return false;
}


signed main(){
    int n, m;
    cin >> n >> m;
    vector<int> x(n), y(n), z(n);
    vector<vector<int>> v(n, vector<int>(8, 0));
    for(int i = 0; i < n; ++i){
        cin >> x[i] >> y[i] >> z[i];
        for(int j = 0; j < 8; ++j){
            v[i][j] += x[i] * (j & 1 ? -1 : 1);
            v[i][j] += y[i] * (j & 2 ? -1 : 1);
            v[i][j] += z[i] * (j & 4 ? -1 : 1);
        }
    }
    vector<vector<int>> edges(n);
    for(int i = 0; i < m; ++i){
        int p, q;
        cin >> p >> q;
        --p, --q;
        edges[q].push_back(p);
    }
    Result res = scc_dag(edges);
    int k = res.dag_size;
    vector<vector<int>> dp(k, vector<int>(8, -MOD));
    for(int i = 0; i < n; ++i)
        for(int j = 0; j < 8; ++j)
            chmax(dp[res.elements[i]][j], v[i][j]);

    for(auto i : res.tps_order){
        for(int j = 0; j < 8; ++j){
            for(auto nex : res.dag_graph[i]){
                chmax(dp[nex][j], dp[i][j]);
            }
        }
    }

    for(int i = 0; i < n; ++i){
        int dist = 0;
        for(int j = 0; j < 8; ++j){
            chmax(dist, dp[res.elements[i]][j] - v[i][j]);
        }
        cout << dist << endl;
    }
}

Traceback (most recent call last):
  File "/opt/hostedtoolcache/Python/3.9.0/x64/lib/python3.9/site-packages/onlinejudge_verify/documentation/build.py", line 71, in _render_source_code_stat
    bundled_code = language.bundle(stat.path, basedir=basedir, options={'include_paths': [basedir]}).decode()
  File "/opt/hostedtoolcache/Python/3.9.0/x64/lib/python3.9/site-packages/onlinejudge_verify/languages/cplusplus.py", line 193, in bundle
    bundler.update(path)
  File "/opt/hostedtoolcache/Python/3.9.0/x64/lib/python3.9/site-packages/onlinejudge_verify/languages/cplusplus_bundle.py", line 399, in update
    self.update(self._resolve(pathlib.Path(included), included_from=path))
  File "/opt/hostedtoolcache/Python/3.9.0/x64/lib/python3.9/site-packages/onlinejudge_verify/languages/cplusplus_bundle.py", line 258, in _resolve
    raise BundleErrorAt(path, -1, "no such header")
onlinejudge_verify.languages.cplusplus_bundle.BundleErrorAt: bits/stdc++.h: line -1: no such header