Submission #682811

#TimeUsernameProblemLanguageResultExecution timeMemory
682811iskhakkutbilimEvacuation plan (IZhO18_plan)C++14
10 / 100
4077 ms33320 KiB
#include <bits/stdc++.h> using namespace std; #define int long long #define ff first #define ss second #define all(a) a.begin(), a.end() const int N = 1e5; const int M = 1e18; int n, m, k; vector< pair<int, int> > g[N]; int AEC[N], distanc[N]; vector<int> A, B; set< pair<int, int> > q; void dijkstra(int start, vector<int>&dis){ for(int i = 0;i < n; i++) dis[i] = (i == start ? 0 : M); q.insert({dis[start], start}); while(!q.empty()){ int v = q.begin()->ss; q.erase(q.begin()); for(auto [to, len] : g[v]){ if(dis[to] > dis[v] + len){ q.erase({dis[to], to}); dis[to] = dis[v]+len; q.insert({dis[to], to}); if(AEC[start]==0 and AEC[to] == 1){ distanc[start] = min(distanc[start], dis[to]); } if(AEC[start]==1 and AEC[to] == 0){ distanc[to] = min(distanc[to], dis[to]); } } } } } int used[N]; int s, t, ans; void dfs(int v){ used[v] = 1; if(v == t){ int mn = M; for(int i = 0;i < n; i++){ if(used[i] == 1){ if(AEC[i] == 1) mn = 0; else mn = min(mn, distanc[i]); } } ans = max(ans, mn); } for(auto [to, len] : g[v]){ if(used[to] == 0){ dfs(to); } } used[v] = 0; } main(){ ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); cin >> n >> m; for(int i = 0;i < m; i++){ int a, b, w; cin >> a >> b >> w; a--, b--; g[a].push_back({b, w}); g[b].push_back({a, w}); } vector<int> dis(n); cin >> k; for(int i = 0;i < k; i++){ int a; cin >> a; a--; AEC[a] = 1; } for(int i = 0;i < n; i++){ distanc[i] = M; if(AEC[i] == 0) B.push_back(i); else A.push_back(i); } if(k > (int)sqrt(n)){ for(int start : B){ dijkstra(start, dis); } }else{ for(int start : A){ dijkstra(start, dis); } } int Q; cin >> Q; while(Q--){ int a, b; cin >> a >> b; a--, b--; if(AEC[a] == 1 or AEC[b] == 1){ cout << 0 << '\n'; }else{ if(n <= 15 and m <= 200){ s = a, t = b, ans = -M; for(int i = 0;i < n; i++) used[i] = 0; dfs(a); cout << ans << '\n'; }else{ cout << min(distanc[a], distanc[b]) << '\n'; } } } return 0; }

Compilation message (stderr)

plan.cpp: In function 'void dijkstra(long long int, std::vector<long long int>&)':
plan.cpp:23:12: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   23 |   for(auto [to, len] : g[v]){
      |            ^
plan.cpp: In function 'void dfs(long long int)':
plan.cpp:55:11: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   55 |  for(auto [to, len] : g[v]){
      |           ^
plan.cpp: At global scope:
plan.cpp:63:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   63 | main(){
      | ^~~~
#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...