Submission #82509

#TimeUsernameProblemLanguageResultExecution timeMemory
82509GoodEvacuation plan (IZhO18_plan)C++11
19 / 100
3339 ms20788 KiB
#include <algorithm> #include <iostream> #include <string.h> #include <stdio.h> #include <vector> #include <queue> #include <cmath> #include <set> #include <map> #define N 100010 #define ff first #define ss second #define pb push_back #define ll long long #define pii pair <int, int> using namespace std; int k; int n, m, q; int a, b, c; int ans[N]; int Par[N]; int L[N], R[N]; int v[N], vis[N]; pii p[N * 5], P[N * 5]; vector <pii> E[N]; priority_queue <pii, vector <pii>, greater <pii>> Q; int ata(int x) { if (x == Par[x]) return x; return Par[x] = ata(Par[x]); } void uni(int x, int y) { x = ata(x); y = ata(y); if (x == y) return; Par[y] = x; } int main() { cin >> n >> m; for(int i = 1; i <= n; i++) L[i] = 0, R[i] = 1e9, v[i] = 1e9; for(int i = 1; i <= m; i++) { cin >> a >> b >> c; E[a].pb({b, c}); E[b].pb({a, c}); } cin >> k; for(int i = 1; i <= k; i++) { cin >> a; Q.push({0, a}), v[a] = 0; } while(!Q.empty()) { pii p = Q.top(); Q.pop(); if(vis[p.ss] == 1) continue; vis[p.ss] = 1; for(auto i: E[p.ss]) if (i.ss + p.ff < v[i.ff]) v[i.ff] = i.ss + p.ff, Q.push({v[i.ff], i.ff}); } for(int i = 1; i <= n; i++) P[i] = {v[i], i}; sort(P+1, P+n+1); cin >> q; for(int i = 1; i <= q; i++) cin >> p[i].ff >> p[i].ss; P[0] = {-1, -1}; for(int j = 1; j <= 31; j++) { set <pii> M; for(int i = 1; i <= n; i++) Par[i] = i; for(int i = 1; i <= q; i++) if (L[i] <= R[i]) M.insert({(L[i] + R[i])/2, i}); memset(vis, 0, sizeof (vis)); for(int i = n; i >= 1; i--) { int nd = P[i].ss; vis[nd] = 1; for(auto h: E[nd]) if (vis[h.ff] == 1) uni(nd, h.ff); if (!M.empty()) { pii last = *M.rbegin(); while(!M.empty() && last.ff > P[i-1].ff) { a = p[last.ss].ff; b = p[last.ss].ss; if (ata(a) == ata(b)) ans[last.ss] = last.ff, L[last.ss] = last.ff + 1; else R[last.ss] = last.ff - 1; M.erase(last); if(!M.empty()) last = *M.rbegin(); } } } } for(int i = 1; i <= q; i++) cout << ans[i] << '\n'; } /* 10 13 1 10 20 4 9 14 5 6 10 9 7 10 7 8 8 7 6 7 4 5 5 10 9 5 10 3 3 3 4 3 10 7 3 2 3 2 1 2 1 2 9 8 2 3 6 4 7 */
#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...