Submission #72609

#TimeUsernameProblemLanguageResultExecution timeMemory
72609claudyElection Campaign (JOI15_election_campaign)C++14
100 / 100
999 ms141968 KiB
# pragma GCC optimize("O3") # include <bits/stdc++.h> std::pair<int,int> DR[] = {{-1,0},{0,1},{1,0},{0,-1},{-1,1},{-1,-1},{1,1},{1,-1}}; # define ll long long # define clock (clock() * 1000.0 / CLOCKS_PER_SEC) # define rc(s) return cout << s,0 # define rcg(s) cerr << s;exit(0) # define _ ios_base::sync_with_stdio(false);cin.tie(0);cerr.tie(0);cout.tie(0); # define db(x) cerr << #x << " = " << x << '\n' # define pb push_back # define mp make_pair # define all(s) s.begin(),s.end() # define sz(x) (int)((x).size()) # define int ll using namespace std; int tin[1 << 17],tout[1 << 17],p[1 << 17][17]; vector<int>vec[1 << 17]; vector<pair<int,int>>clad[1 << 17]; int timer; int n,a,b,c; int depth[1 << 17],s[1 << 17][17]; int dp[1 << 17],sum[1 << 17]; struct data { int a,b,c; }; vector<data>t[1 << 17]; bool upper(int a,int b) { return (tin[a] <= tin[b] && tout[a] >= tout[b]); } int lca(int a,int b) { if(upper(a,b)) return a; if(upper(b,a)) return b; for(int l = 16;l + 1;l--) { if(!upper(p[a][l],b)) a = p[a][l]; } return p[a][0]; } void predfs(int nod,int par) { depth[nod] = depth[par] + 1; tin[nod] = timer++; p[nod][0] = par; clad[par].pb(mp(nod,0)); for(int l = 1;l <= 16;l++) { p[nod][l] = p[p[nod][l - 1]][l - 1]; clad[p[nod][l]].pb(mp(nod,l)); } for(auto it : vec[nod]) { if(it != par) { predfs(it,nod); } } tout[nod] = timer++; } int f(int nod,int len) { len--; if(len == -1) return 0; int ans = sum[nod] - dp[nod]; for(int i = 16;i >= 0;i--) { if(len & (1 << i)) { ans += s[nod][i]; ans -= sum[nod] - dp[nod]; nod = p[nod][i]; } } return ans; } void put(int nod) { int x = sum[nod] - dp[nod]; for(auto it : clad[nod]) { if(it.second == 0) { s[it.first][0] = x + sum[it.first] - dp[it.first]; } else { s[it.first][it.second] = s[it.first][it.second - 1] + s[p[it.first][it.second - 1]][it.second - 1] - sum[p[it.first][it.second - 1]] + dp[p[it.first][it.second - 1]]; } } } void dfs(int nod,int par) { for(auto it : vec[nod]) { if(it != par){ dfs(it,nod); sum[nod] += dp[it]; } } dp[nod] = sum[nod]; int mx = sum[nod]; for(auto it : t[nod]) { mx = max(mx,it.c + sum[nod] + f(it.a,depth[it.a] - depth[nod]) + f(it.b,depth[it.b] - depth[nod])); } dp[nod] = mx; put(nod); } int32_t main(){_ //freopen("input","r",stdin); cin >> n; for(int i = 1;i < n;i++) { cin >> a >> b; a--; b--; vec[a].pb(b); vec[b].pb(a); } predfs(0,0); int q; cin >> q; while(q--) { cin >> a >> b >> c; a--; b--; t[lca(a,b)].pb({a,b,c}); } dfs(0,0); rc(dp[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...
#Verdict Execution timeMemoryGrader output
Fetching results...