Submission #253778

#TimeUsernameProblemLanguageResultExecution timeMemory
253778someoneElection Campaign (JOI15_election_campaign)C++14
100 / 100
271 ms47356 KiB
#include <bits/stdc++.h> #define int long long using namespace std; struct Way { int a, b, cost; }; const int M = 1 << 18, N = 2*M; vector<int> adj[M]; vector<Way> way[M]; int n, m, l = M, deb[M], fin[M], sum[M], a[N], par[N][19]; void DFS(int i, int pre) { deb[i] = l++; par[i][0] = pre; for(int j : adj[i]) if(j != pre) DFS(j, i); fin[i] = l++; } bool isAnc(int a, int b) { if(a == -1) return true; return deb[a] <= deb[b] && fin[b] <= fin[a]; } int LCA(int a, int b) { if(isAnc(a, b)) return a; if(isAnc(b, a)) return b; for(int i = 18; i > -1; i--) if(!isAnc(par[a][i], b)) a = par[a][i]; return par[a][0]; } int getSum(int i) { int t = a[i]; while(i > 0) { if(i % 2 == 1) t += a[i-1]; i /= 2; } return t; } void insert(int i, int val) { while(i > 0) { a[i] += val; i /= 2; } } int get(int i) { for(int j : adj[i]) if(j != par[i][0]) sum[i] += get(j); int val = 0; for(Way w : way[i]) val = max(val, w.cost - getSum(deb[w.a]) - getSum(deb[w.b])); sum[i] += val; insert(deb[i], val); insert(fin[i], -val); return sum[i]; } signed main() { /* freopen("input.txt", "r", stdin); freopen("output.txt", "w", stdout); */ ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); cin >> n; for(int i = 1; i < n; i++) { int a, b; cin >> a >> b; a--, b--; adj[a].push_back(b); adj[b].push_back(a); } DFS(0, -1); for(int i = 0; i < 18; i++) for(int j = 0; j < n; j++) if(par[j][i] == -1) par[j][i+1] = -1; else par[j][i+1] = par[par[j][i]][i]; cin >> m; for(int i = 0; i < m; i++) { int a, b, cost; cin >> a >> b >> cost; a--, b--; int c = LCA(a, b); way[c].push_back({a, b, cost}); } cout << get(0) << '\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...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...