Submission #332202

#TimeUsernameProblemLanguageResultExecution timeMemory
332202vitkishloh228Evacuation plan (IZhO18_plan)C++14
31 / 100
1228 ms60780 KiB
#include<iostream> #include<vector> #include<algorithm> #include<set> #define int long long using namespace std; int logn = 20; vector<vector<int>> t; vector<int> p, sz; int getp(int v) { if (p[v] == v) return v; return p[v] = getp(p[v]); } void unite(int a, int b) { int a0 = a; a = getp(a); b = getp(b); if (a != b) { t[a].push_back(b); t[b].push_back(a); p[a] = b; //sz[a] += sz[b]; } } vector<int> tin, tout; int timer = 0; vector<vector<int>> up; void dfs(int v, int p = -1) { tin[v] = timer++; for (int i = 1; i < logn; ++i) { up[v][i] = up[up[v][i - 1]][i - 1]; } for (auto u : t[v]) { if (u != p) { up[u][0] = v; dfs(u, v); } } tout[v] = timer; } bool par(int a, int b) { return (tin[a] <= tin[b] && tin[b] < tout[a]); } int lca(int a, int b) { if (par(a, b)) return a; if (par(b, a)) return b; for (int i = logn - 1; i >= 0; i--) { if (!par(up[a][i], b)) { a = up[a][i]; } } return up[a][0]; } int32_t main() { int n, m; cin >> n >> m; vector < vector<pair<int, int>>> g(n); while (m--) { int a, b, c; cin >> a >> b >> c; --a, --b; g[a].push_back({ b,c }); g[b].push_back({ a,c }); } set<pair<int, int>> q; int k; cin >> k; vector<int> d(n, 1e17); while (k--) { int v; cin >> v; --v; d[v] = 0; q.insert({ 0,v }); } while (q.size()) { int v = q.begin()->second; q.erase(q.begin()); for (auto u : g[v]) { // cout << "fuck\n"; if (d[u.first] > d[v] + u.second) { q.erase({ d[u.first],u.first }); d[u.first] = d[v] + u.second; q.insert({ d[u.first],u.first }); } } } //for (auto elem : d) cout << elem << ' '; //cout << endl; vector<pair<int, int>> arr(n); for (int i = 0; i < n; ++i) { arr[i] = { d[i],i }; } sort(arr.begin(), arr.end()); reverse(arr.begin(), arr.end()); p = vector<int>(n); sz = vector<int>(n, 1); for (int i = 0; i < n; ++i) { p[i] = i; } tin.resize(n); tout.resize(n); up = vector<vector<int>>(n, vector<int>(logn, arr.back().second)); t.resize(n); for (auto elem : arr) { for (auto u : g[elem.second]) { if (d[elem.second]<d[u.first]) unite(u.first, elem.second); } } dfs(arr.back().second); int Q; cin >> Q; while (Q--) { int s, t; cin >> s >> t; --s, --t; int v = lca(s, t); cout << d[v] << '\n'; } }

Compilation message (stderr)

plan.cpp: In function 'void unite(long long int, long long int)':
plan.cpp:15:9: warning: unused variable 'a0' [-Wunused-variable]
   15 |     int a0 = a;
      |         ^~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...