제출 #892075

#제출 시각아이디문제언어결과실행 시간메모리
892075kh0iEvacuation plan (IZhO18_plan)C++17
100 / 100
370 ms146680 KiB
#include "bits/stdc++.h" using namespace std; #ifdef LOCAL #include "debug.h" #else #define debug(...) #endif using ll = long long; using pii = pair<int, int>; #define F first #define S second #define sz(x) (int)((x).size()) #define all(x) (x).begin(), (x).end() mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count()); ll get_rand(ll l, ll r) { assert(l <= r); return uniform_int_distribution<ll> (l, r)(rng); } const int N = 1e5 + 3; int n, m, k, q; int p[N]; ll dist[N]; vector<pair<int, ll>> g[N]; struct DSU_Rollback{ struct Data{ int u, sz_u, v, sz_v; }; int n; vector<int> p, sz; vector<Data> op; int comps; void init(int _n){ n = _n; p.clear(); sz.clear(); p.resize(n + 2, 0); sz.resize(n + 2, 1); comps = n; iota(all(p), 0); } // no path compression int find_set(int u){ return u == p[u] ? u : find_set(p[u]); } bool join_sets(int u, int v){ u = find_set(u); v = find_set(v); if(u == v) return 0; --comps; if(sz[u] < sz[v]) swap(u, v); op.push_back({u, sz[u], v, sz[v]}); p[v] = u; sz[u] += sz[v]; return 1; } bool same_set(int u, int v){ return find_set(u) == find_set(v); } void rollback(){ if(op.empty()) return; Data &x = op.back(); p[x.u] = x.u; p[x.v] = x.v; sz[x.u] = x.sz_u; sz[x.v] = x.sz_v; ++comps; op.pop_back(); } }; namespace Sub12{ bool valid_input(){ return (n <= 20 and m <= 200 and q <= 200) or q == 1; } void dijkstra(){ priority_queue<pair<ll, int>> pq; memset(dist, 0x3f3f3f3f, sizeof(dist)); for(int i = 1; i <= k; ++i){ dist[p[i]] = 0; pq.push({-dist[p[i]], p[i]}); } while(!pq.empty()){ int u = pq.top().S; pq.pop(); for(auto [v, w] : g[u]){ if(dist[v] > dist[u] + w){ dist[v] = dist[u] + w; pq.push({-dist[v], v}); } } } } void solve(){ dijkstra(); for(int i = 1; i <= n; ++i) debug(i, dist[i]); DSU_Rollback dsu; while(q--){ int s, t; cin >> s >> t; ll l = 0, r = 1e14, res = 1e14; while(l <= r){ ll mid = (l + r) / 2; dsu.init(n); for(int i = 1; i <= n; ++i) if(dist[i] >= mid) for(auto [v, w] : g[i]) if(dist[v] >= mid) dsu.join_sets(i, v); if(dsu.same_set(s, t)){ res = mid; l = mid + 1; } else r = mid - 1; } cout << res << '\n'; } } } struct Edge{ int u, v; ll mn; }; struct Query{ int s, t, id; }; vector<Query> d; vector<Edge> e; map<int, int> mp[N]; namespace Sub3{ DSU_Rollback dsu; vector<ll> dif_dist; ll ans[N]; void calc(int l, int r, vector<Edge> &e, vector<Query> &d){ if(l + 1 == r or d.empty()){ for(auto& [s, t, id] : d) ans[id] = dif_dist[l]; return; } int mid = (l + r) / 2; ll mxw = dif_dist[mid]; vector<Edge> el, er; vector<Query> dl, dr; int cnt_add = 0; for(auto &x : e){ if(x.mn >= mxw){ cnt_add += dsu.join_sets(x.u, x.v); er.push_back(x); } else el.push_back(x); } for(auto &x : d){ if(dsu.same_set(x.s, x.t)) dr.push_back(x); else dl.push_back(x); } calc(l, mid, el, dl); while(cnt_add--) dsu.rollback(); calc(mid, r, er, dr); } void dijkstra(){ priority_queue<pair<ll, int>> pq; memset(dist, 0x3f3f3f3f, sizeof(dist)); for(int i = 1; i <= k; ++i){ dist[p[i]] = 0; pq.push({-dist[p[i]], p[i]}); } while(!pq.empty()){ int u = pq.top().S; pq.pop(); for(auto [v, w] : g[u]){ if(dist[v] > dist[u] + w){ dist[v] = dist[u] + w; pq.push({-dist[v], v}); } } } } void solve(){ dsu.init(n); dijkstra(); for(int i = 1; i <= n; ++i) for(auto& [v, w]: g[i]) if(i > v) e.push_back({i, v, min(dist[i], dist[v])}); for(int i = 1; i <= q; ++i){ int s, t; cin >> s >> t; d.push_back({s, t, i}); } for(int i = 1; i <= n; ++i) dif_dist.push_back(dist[i]); sort(all(dif_dist)); dif_dist.resize(unique(all(dif_dist)) - dif_dist.begin()); calc(0, sz(dif_dist), e, d); for(int i = 1; i <= q; ++i) cout << ans[i] << '\n'; } } void read_input(){ cin >> n >> m; for(int i = 1; i <= m; ++i){ int u, v, w; cin >> u >> v >> w; if(u == v) continue; g[u].push_back({v, w}); g[v].push_back({u, w}); } cin >> k; for(int i = 1; i <= k; ++i) cin >> p[i]; cin >> q; } void solve(){ read_input(); #ifdef LOCAL cerr << "\n[Input Time]: " << 1000.0 * clock() / CLOCKS_PER_SEC << " ms.\n"; #endif Sub3::solve(); } int32_t main() { cin.tie(nullptr)->sync_with_stdio(0); #define task "troll" if(fopen(task".inp", "r")){ freopen(task".inp", "r", stdin); freopen(task".out", "w", stdout); } int test = 1; // cin >> test; for(int i = 1; i <= test; ++i){ // cout << "Case #" << i << ": "; solve(); } #ifdef LOCAL cerr << "\n[Time]: " << 1000.0 * clock() / CLOCKS_PER_SEC << " ms.\n"; #endif return 0; }

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

plan.cpp: In function 'int32_t main()':
plan.cpp:272:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  272 |         freopen(task".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
plan.cpp:273:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  273 |         freopen(task".out", "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...