제출 #525185

#제출 시각아이디문제언어결과실행 시간메모리
525185Dilshod_ImomovEvacuation plan (IZhO18_plan)C++17
100 / 100
713 ms42436 KiB
# include <bits/stdc++.h> # define speed ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0) // # define int long long # define fi first # define se second using namespace std; const int N = 1e5 + 7; const int mod = 1e9 + 7; // const int INF = 1e18; vector < pair < int, int > > adj[N]; int d[N], used[N], sz[N], pr[N], ans[N]; set < int > qr[N]; int find_set( int a ) { if ( pr[a] == a ) { return a; } return pr[a] = find_set(pr[a]); } void merge( int a, int b, int val ) { a = find_set(a); b = find_set(b); if ( a == b ) { return; } if ( sz[a] < sz[b] ) { swap( a, b ); } // cout << a << ' ' << b << ' ' << val << endl; for ( auto i: qr[b] ) { if ( qr[a].find(i) != qr[a].end() ) { // cout << i << endl; ans[i] = val; qr[a].erase(i); } else { qr[a].insert(i); } } qr[b].clear(); sz[a] += sz[b]; pr[b] = a; } int32_t main() { speed; int n, m; cin >> n >> m; for ( int i = 1; i <= m; i++ ) { int u, v, w; cin >> u >> v >> w; adj[u].push_back({v, w}); adj[v].push_back({u, w}); } int k; cin >> k; set < pair < int, int > > st; for ( int i = 1; i <= n; i++ ) { d[i] = mod; pr[i] = i; sz[i] = 1; } for ( int i = 1; i <= k; i++ ) { int x; cin >> x; d[x] = 0; st.insert({0, x}); } while ( !st.empty() ) { int v = st.begin()->se; st.erase( { d[v], v } ); // cout << v << " " << d[v] << endl; for ( auto pr: adj[v] ) { int u = pr.fi, w = pr.se; if ( d[v] + w < d[u] ) { st.erase( { d[u], u } ); d[u] = d[v] + w; st.insert( { d[u], u } ); } } } int q; cin >> q; for ( int i = 1; i <= q; i++ ) { int u, v; cin >> u >> v; qr[u].insert(i); qr[v].insert(i); } vector < pair < int, int > > vc; for ( int i = 1; i <= n; i++ ) { vc.push_back( { d[i], i } ); } sort( vc.rbegin(), vc.rend() ); for ( int i = 0; i < n; i++ ) { int v = vc[i].se; used[v] = 1; // cout << "-> " << v << ' ' << d[v] << endl; for ( auto pr: adj[v] ) { int u = pr.fi; if ( used[u] ) { // cout << v << ' ' << u << endl; merge(v, u, d[v]); } } } for ( int i = 1; i <= q; i++ ) { cout << ans[i] << "\n"; } } /* 9 12 1 9 4 1 2 5 2 3 7 2 4 3 4 3 6 3 6 4 8 7 10 6 7 5 5 8 1 9 5 7 5 4 12 6 8 2 2 4 7 5 1 6 5 3 4 8 5 8 1 5 */
#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...