제출 #200558

#제출 시각아이디문제언어결과실행 시간메모리
200558johuthaValley (BOI19_valley)C++14
0 / 100
588 ms24296 KiB
#include <vector> #include <iostream> #define int int64_t using namespace std; int log2(int n) { int res = 0; for (; n; n >>= 1) res++; return res; } struct graph { vector<vector<pair<int,int>>> adjlist; vector<vector<int>> lcatable; vector<int> lvl; int n; int logn; vector<bool> shop; void builddfs(int curr, int par, int l) { lvl[curr] = l; lcatable[0][curr] = par; for (auto p : adjlist[curr]) { auto next = p.first; if (next == par) continue; builddfs(next, curr, l + 1); } } void build() { logn = log2(n); lcatable.resize(logn, vector<int>(n)); lvl.resize(n, - 1); builddfs(0, -1, 0); for (int l = 1; l < logn; l++) { for (int i = 0; i < n; i++) { lcatable[l][i] = (lcatable[l - 1][i] == -1) ? -1 : lcatable[l - 1][lcatable[l - 1][i]]; } } } int lca(int a, int b) { if (lvl[a] < lvl[b]) swap(a, b); int ldiff = lvl[a] - lvl[b]; int e = 1; for (int i = 0; i < logn; i++) { if (ldiff & e) a = lcatable[i][a]; e *= 2; } if (a == b) return a; for (int i = 0; i < logn; i++) { if (lcatable[i][a] != lcatable[i][b]) { a = lcatable[i][a]; b = lcatable[i][b]; } } return lcatable[0][a]; } int ddfs(int curr, int par, pair<int,int> fb) { // cerr << curr << " " << shop[curr] << "\n"; if (shop[curr] == true) return 0; int mmin = 1e15; for (auto p : adjlist[curr]) { int next = p.first; if (next == par) continue; if (min(fb.first, fb.second) == min(curr, next) && max(fb.first, fb.second) == max(curr, next)) continue; mmin = min(mmin, p.second + ddfs(next, curr, fb)); } return mmin; } }; signed main() { int n, s, q, r; cin >> n >> s >> q >> r; graph g; g.n = n; g.adjlist.resize(n); g.shop.resize(n, false); vector<pair<int,int>> edges; for (int i = 0; i < n - 1; i++) { int a, b, w; cin >> a >> b >> w; a--; b--; edges.emplace_back(a, b); g.adjlist[a].emplace_back(b, w); g.adjlist[b].emplace_back(a, w); } for (int i = 0; i < s; i++) { int p; cin >> p; p--; g.shop[p] = true; } g.build(); for (int i = 0; i < q; i++) { int r, v; cin >> r >> v; r--; v--; auto p = edges[r]; if (g.lvl[p.first] > g.lvl[p.second]) swap(p.first, p.second); if (g.lca(p.second, v) != p.second) { cout << "escaped\n"; continue; } int d = g.ddfs(v, -1, p); if (d >= 1e5) { cout << "oo\n"; } else { cout << d << "\n"; } } }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...