제출 #900232

#제출 시각아이디문제언어결과실행 시간메모리
900232stefanneaguRoadside Advertisements (NOI17_roadsideadverts)C++17
100 / 100
164 ms12952 KiB
#include <bits/stdc++.h> using namespace std; const int nmax = 1e5 + 1; vector<vector<pair<int, int>>> adj; int u[nmax][17], d[nmax], e[nmax], depth[nmax], v[6], fin, cnt = 1; void dfs(int i, int tata) { u[i][0] = tata; e[i] = cnt; cnt ++; for(auto it : adj[i]) { if(it.first != tata) { d[it.first] = d[i] + it.second; depth[it.first] = depth[i] + 1; dfs(it.first, i); } } } int get(int a, int x) { for(int i = 0; (1 << i) <= x; i ++) { if((1 << i) & x) { a = u[a][i]; } } return a; } int lca(int a, int b) { if(depth[a] > depth[b]) { swap(a, b); } int l = 0, r = depth[a], ans = 0; while(l <= r) { int mid = (l + r) / 2; if(get(a, mid) == get(b, mid + depth[b] - depth[a])) { ans = get(a, mid); r = mid - 1; } else { l = mid + 1; } } return ans; } int sum(int x, int y) { return d[x] + d[y] - 2 * d[lca(x, y)]; } bool cmp(int a, int b) { return e[a] < e[b]; } void testcase() { for(int i = 1; i <= 5; i ++) { cin >> v[i]; v[i] ++; } sort(v + 1, v + 6, cmp); int ans = sum(lca(v[1], v[5]), v[1]); for(int i = 2; i <= 5; i ++) { ans += sum(lca(v[i - 1], v[i]), v[i]); } //assert(ans == fin); cout << ans << '\n'; } int main() { int n; cin >> n; adj.resize(n + 1); for(int i = 1; i < n; i ++) { int a, b, c; cin >> a >> b >> c; a ++, b ++; adj[a].push_back({b, c}); adj[b].push_back({a, c}); fin += c; } dfs(1, 0); for(int j = 1; (1 << j) <= n; j ++) { for(int i = 1; i <= n; i ++) { if(depth[i] >= (1 << j)) { u[i][j] = u[u[i][j - 1]][j - 1]; } } } int q; cin >> q; for(int tt = 1; tt <= q; tt ++) { testcase(); } 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...