제출 #501360

#제출 시각아이디문제언어결과실행 시간메모리
501360NachoLibreEvacuation plan (IZhO18_plan)C++17
100 / 100
576 ms36868 KiB
#include <bits/stdc++.h> #define ll long long #define ld long double #define sz(x) ((int)(x).size()) #define all(x) (x).begin(), (x).end() using namespace std; const int N = 100005, M = 17; vector<int> dyup(N, -1); int up[N][M]; int P(int x) { return dyup[x] < 0 ? x : dyup[x] = P(dyup[x]); } void H(int x, int y) { if(P(y) == x) return; up[P(y)][0] = x; dyup[P(y)] = x; } int main() { ios::sync_with_stdio(0); cin.tie(0); #ifdef wambule freopen("Untitledfile.txt", "r", stdin); #endif int n, m; cin >> n >> m; vector<array<int, 2>> v1[n + 1]; for(int i = 1; i <= m; ++i) { int x, y, z; cin >> x >> y >> z; v1[x].push_back({y, z}); v1[y].push_back({x, z}); } int k; cin >> k; set<array<int, 2>> s1; vector<int> d(n + 1, -1); for(int i = 1; i <= k; ++i) { int x; cin >> x; s1.insert({0, x}); d[x] = 0; } while(s1.size()) { int x = (*s1.begin())[1]; s1.erase(s1.begin()); for(auto y : v1[x]) { if(d[y[0]] == -1 || d[y[0]] > d[x] + y[1]) { if(d[y[0]] != -1) s1.erase({d[y[0]], y[0]}); d[y[0]] = d[x] + y[1]; s1.insert({d[y[0]], y[0]}); } } } vector<array<int, 2>> v2; for(int i = 1; i <= n; ++i) { v2.push_back({d[i], i}); } sort(all(v2)); reverse(all(v2)); vector<bool> cc(n + 1); for(auto x : v2) { cc[x[1]] = 1; for(auto y : v1[x[1]]) { if(!cc[y[0]]) continue; H(x[1], y[0]); } } for(int j = 1; j < M; ++j) { for(int i = 1; i <= n; ++i) { up[i][j] = up[up[i][j - 1]][j - 1]; } } vector<int> dt(n + 1); for(int i = 1; i <= n; ++i) { int x = i; for(int j = M - 1; j >= 0; --j) { if(up[x][j] != 0) { x = up[x][j]; dt[i] |= (1 << j); } } } int q; cin >> q; for(int i = 1; i <= q; ++i) { int x, y; cin >> x >> y; if(dt[x] < dt[y]) { swap(x, y); } for(int j = M - 1; j >= 0; --j) { if(dt[x] - (1 << j) >= dt[y]) { x = up[x][j]; } } int ap = 0; if(x == y) { ap = d[x]; } else { for(int j = M - 1; j >= 0; --j) { if(up[x][j] != up[y][j]) { x = up[x][j]; y = up[y][j]; } } ap = d[up[x][0]]; } cout << ap << "\n"; } 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...