제출 #947260

#제출 시각아이디문제언어결과실행 시간메모리
947260nguyennhEvacuation plan (IZhO18_plan)C++14
100 / 100
408 ms48628 KiB
#include<bits/stdc++.h> #define el '\n' using namespace std ; mt19937 rd(chrono::steady_clock::now().time_since_epoch().count()); const int MN = 1e5 + 5; const int N = 5e5 + 5; const int inf = 1e9; int dis[MN] , l[MN] , r[MN]; vector<pair<int , int>> adj[MN]; vector<int> candidates[MN]; pair<int , pair<int , int>> edge[N]; pair<int , int> queries[MN] , cur[MN]; struct DSU{ vector<int> par , sz; int n; void init(int n){ this -> n = n; par.resize(n + 5); sz.resize(n + 5 , 1); for ( int i = 1 ; i <= n ; i++ ) par[i] = i; } int find_set(int v){ return v == par[v] ? v : par[v] = find_set(par[v]); } void unite(int r , int s){ r = find_set(r) , s = find_set(s); if (r != s){ if (sz[r] < sz[s]) swap(r , s); par[s] = r; sz[r] += sz[s]; } } bool same_set(int u , int v){ return find_set(u) == find_set(v); } }; int32_t main (){ ios_base::sync_with_stdio(0); cin.tie(0); int n , m; cin >> n >> m; for ( int i = 0 ; i < m ; i++ ){ int u , v , w; cin >> u >> v >> w; adj[u].push_back(make_pair(v , w)); adj[v].push_back(make_pair(u , w)); edge[i].second = make_pair(u , v); } priority_queue<pair<int , int> , vector<pair<int , int>> , greater<pair<int , int>>> pq; for ( int i = 1 ; i <= n ; i++ ) dis[i] = inf; int k; cin >> k; for ( int i = 1 ; i <= k ; i++ ){ int x; cin >> x; dis[x] = 0; pq.push(make_pair(0 , x)); } while (!pq.empty()){ auto [d , u] = pq.top(); pq.pop(); if (d != dis[u]) continue; for ( auto [v , w] : adj[u] ){ if (dis[v] > dis[u] + w){ dis[v] = dis[u] + w; pq.push(make_pair(dis[v] , v)); } } } for ( int i = 0 ; i < m ; i++ ) edge[i].first = min(dis[edge[i].second.first] , dis[edge[i].second.second]); int q; cin >> q; for ( int i = 0 ; i < q ; i++ ){ cin >> queries[i].first >> queries[i].second; } for ( int i = 1 ; i <= n ; i++ ) cur[i] = make_pair(dis[i] , i); sort(cur + 1 , cur + n + 1); sort(edge , edge + m); DSU dsu; for ( int i = 0 ; i < q ; i++ ){ l[i] = 1; r[i] = n; } while (1){ bool any = false; for ( int i = 0 ; i < q ; i++ ){ if (l[i] <= r[i]){ int mid = (l[i] + r[i]) / 2; candidates[mid].push_back(i); any = true; } } if (!any) break; dsu.init(n); int j = m - 1; for ( int mid = n ; mid >= 1 ; mid-- ){ while (j >= 0 && edge[j].first >= cur[mid].first){ dsu.unite(edge[j].second.first , edge[j].second.second); j--; } for ( auto x : candidates[mid] ){ if (dsu.same_set(queries[x].first , queries[x].second)){ l[x] = mid + 1; } else r[x] = mid - 1; } candidates[mid].clear(); } } for ( int i = 0 ; i < q ; i++ ) cout << cur[r[i]].first << el; }

컴파일 시 표준 에러 (stderr) 메시지

plan.cpp: In function 'int32_t main()':
plan.cpp:69:10: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   69 |     auto [d , u] = pq.top();
      |          ^
plan.cpp:72:16: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   72 |     for ( auto [v , w] : adj[u] ){
      |                ^
#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...