제출 #945894

#제출 시각아이디문제언어결과실행 시간메모리
945894sysiaEvacuation plan (IZhO18_plan)C++17
100 / 100
761 ms67356 KiB
//Sylwia Sapkowska #include <bits/stdc++.h> #pragma GCC optimize("O3", "unroll-loops") using namespace std; void __print(int x) {cerr << x;} void __print(long long x) {cerr << x;} void __print(long double x) {cerr << x;} void __print(char x) {cerr << "'" << x << "'";} void __print(const char *x) {cerr << '"' << x << '"';} void __print(const string &x) {cerr << '"' << x << '"';} void __print(bool x) {cerr << (x ? "true" : "false");} template<typename T, typename V> void __print(const pair<T, V> &x) {cerr << '{'; __print(x.first); cerr << ", "; __print(x.second); cerr << '}';} template<typename T> void __print(const T &x) {int f = 0; cerr << '{'; for (auto &i: x) cerr << (f++ ? ", " : ""), __print(i); cerr << "}";} void _print() {cerr << "]\n";} template <typename T, typename... V> void _print(T t, V... v) {__print(t); if (sizeof...(v)) cerr << ", "; _print(v...);} #ifdef LOCAL #define debug(x...) cerr << "[" << #x << "] = ["; _print(x) #else #define debug(x...) #endif #define int long long typedef pair<int, int> T; const int oo = 1e18, oo2 = 1e9+7, K = 30; const int mod = 998244353; struct DSU{ vector<int>rep, sz; DSU(int n){ rep.resize(n+1); sz.resize(n+1); } void clear(){ iota(rep.begin(), rep.end(), 0); sz.assign(sz.size(), 1); } int f(int a){ return a == rep[a] ? a : rep[a] = f(rep[a]); } void u(int a, int b){ a = f(a); b= f(b); if (a == b) return; if (sz[a] < sz[b]) swap(a, b); sz[a] += sz[b]; rep[b] = a; } bool sameset(int a, int b){ return f(a) == f(b); } }; void solve(){ int n, m; cin >> n >> m; vector<vector<T>>g(n+1); vector<T>edges; for (int i = 0; i<m; i++){ int a, b, c; cin >> a >> b >> c; g[a].emplace_back(b, c); g[b].emplace_back(a, c); edges.emplace_back(a, b); } vector<int>dist(n+1, oo); int k; cin >> k; set<T>s; while (k--){ int v; cin >> v; dist[v] = 0; s.insert({0, v}); } while ((int)s.size()){ auto [d, v] = *s.begin(); s.erase(s.begin()); if (dist[v] < d) continue; for (auto [x, c]: g[v]){ if (dist[x] > dist[v] + c){ dist[x] = dist[v]+c; s.insert({dist[x], x}); } } } debug(dist); vector<T>sweep; DSU dsu(n+2); for (int i = 0; i<m; i++){ auto [a, b] = edges[i]; sweep.emplace_back(min(dist[a], dist[b]), i); } sort(sweep.rbegin(), sweep.rend()); debug(sweep); //max odleglosc ze jest sciezka miedzy nimi int q; cin >> q; vector<T>que(q); for (auto &[x, y]: que) cin >> x >> y; vector<int>L(q), R(q, oo2), ans(q, 0); while (1){ bool any = 0; vector<T>tab; for (int i = 0; i<q; i++){ if (R[i] >= L[i]){ tab.emplace_back((L[i]+R[i])/2, i); any = 1; } } if (!any) break; dsu.clear(); sort(tab.rbegin(), tab.rend()); int ptr = -1; for (auto [mid, i]: tab){ while (ptr + 1 < (int)sweep.size() && sweep[ptr+1].first >= mid){ ptr++; auto [a, b] = edges[sweep[ptr].second]; dsu.u(a, b); } if (dsu.sameset(que[i].first, que[i].second)){ ans[i] = mid; L[i] = mid+1; } else R[i] = mid-1; } } for (auto x: ans) cout << x << "\n"; } int32_t main(){ ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); int t = 1; //cin >> t; while (t--) solve(); return 0; }
#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...