제출 #1094376

#제출 시각아이디문제언어결과실행 시간메모리
1094376NurislamEvacuation plan (IZhO18_plan)C++17
100 / 100
440 ms79808 KiB
#include <bits/stdc++.h> // include <ext/pb_ds/assoc_container.hpp> // include <ext/pb_ds/tree_policy.hpp> // using namespace __gnu_pbds; using namespace std; #define all(x) x.begin(), x.end() #define pb push_back // define ordered_set tree<int,null_type,less_equal<int>,rb_tree_tag,tree_order_statistics_node_update> #define mpr make_pair #define ln '\n' void IO(string name){freopen((name+".in").c_str(),"r",stdin); freopen((name+".out").c_str(),"w",stdout);} #define int long long const int N = 1e5+1; vector <pair<int,int>> g[N]; vector <int> G[N]; int lift[N][20], Mn[N][20], val[N], depth[N]; void dfs(int n, int p){ lift[n][0] = p; Mn[n][0] = val[n]; depth[n] = depth[p]+1; for ( int i = 1; i < 20; i++ ){ lift[n][i] = lift[lift[n][i-1]][i-1]; Mn[n][i] = min(Mn[n][i-1], Mn[lift[n][i-1]][i-1]); } for ( auto to: G[n] ){ if ( to == p ) continue; dfs(to, n); } } int _lca(int l, int r){ if ( depth[l] < depth[r] ) swap(l, r); int dif = depth[l]-depth[r], res = numeric_limits <int>::max(); for ( int i = 19; i >= 0; i-- ){ if ( dif >> i & 1 ){ res = min(res, Mn[l][i]); l = lift[l][i]; } } if ( l == r ) return min(res, val[l]); for ( int i = 19; i >= 0; i-- ){ if ( lift[l][i] == lift[r][i] ) continue; res = min({res, Mn[l][i], Mn[r][i]}); l = lift[l][i], r = lift[r][i]; } res = min({res, Mn[l][1], Mn[r][1]}); return res; } signed main(){ ios_base::sync_with_stdio(false); cin.tie(NULL); int n, m; cin >> n >> m; for ( int i = 1; i <= m; i++ ){ int x, y, w; cin >> x >> y >> w; g[x].pb({y, w}); g[y].pb({x, w}); } int k; cin >> k; priority_queue <pair<int,int>> q; const int inf = 1e12+1; vector <int> dis(n+1, inf); for ( int i = 1; i <= k; i++ ){ int x; cin >> x; q.push({0, x}); dis[x] = 0; } while ( !q.empty() ){ int cur = q.top().second; q.pop(); for ( auto [to, w]: g[cur] ){ int new_dis = dis[cur]+w; if ( new_dis < dis[to] ){ dis[to] = new_dis; q.push({-dis[to], to}); } } } vector <int> pos(n+1), par(n+1); iota(all(pos), 0); iota(all(par), 0); sort(pos.begin()+1, pos.end(), [&](int &l, int &r){ return dis[l] > dis[r]; }); for ( int i = 1; i <= n; i++ ) val[i] = dis[i]; function <int(int)> find = [&](int x){ return par[x] == x ? x : par[x] = find(par[x]); }; auto merge = [&](int x, int y){ x = find(x), y = find(y); if ( x == y ) return false; par[y] = x; return true; }; vector <int> used(n+1); for ( auto i: pos ){ if ( !i ) continue; for ( auto [to, w]: g[i] ){ if ( !used[to] ) continue; if ( merge(to, i) ){ G[to].pb(i), G[i].pb(to); } } used[i] = 1; } dfs(1, 0); int Q; cin >> Q; while ( Q-- ){ int x, y; cin >> x >> y; cout << _lca(x, y) << ln; } cout << '\n'; }

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

plan.cpp: In function 'void IO(std::string)':
plan.cpp:11:29: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   11 | void IO(string name){freopen((name+".in").c_str(),"r",stdin); freopen((name+".out").c_str(),"w",stdout);}
      |                      ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
plan.cpp:11:70: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   11 | void IO(string name){freopen((name+".in").c_str(),"r",stdin); freopen((name+".out").c_str(),"w",stdout);}
      |                                                               ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
#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...