Submission #1150031

#TimeUsernameProblemLanguageResultExecution timeMemory
1150031andrewpElection Campaign (JOI15_election_campaign)C++20
100 / 100
142 ms68676 KiB
//Dedicated to my love, ivaziva #include <bits/stdc++.h> using namespace std; #define ll long long #define pb push_back #define pii pair<int,int> #define all(x) x.begin(), x.end() #define rall(x) x.rbegin(), x.rend() #define sz(a) ((int)a.size()) const int N=1e6+5; struct node { int a, b, c; }; int n, m, up[N][20], dep[N], tin[N], tout[N], tajm=1, ft[N]; vector<int> g[N]; ll dp[N][2]; vector<node> pom[N]; void dfs(int x, int p) { dep[x]=dep[p]+1; tin[x]=tajm++; up[x][0]=p; for (int i=1; i<20; i++) up[x][i]=up[up[x][i-1]][i-1]; for (int u:g[x]) { if (u!=p) dfs(u, x); } tout[x]=tajm++; } int raise(int x, int y) { int z=0; while (y) { if (y&1) x=up[x][z]; z++; y>>=1; } return x; } array<int, 3> lca(int a, int b) { if (dep[a]>dep[b]) swap(a, b); int x=dep[b]-dep[a]; int ob=b; b=raise(b, x); if (a==b) return {a, raise(ob, x-1), -1}; for (int i=19; i>=0; i--) { if (up[a][i]!=up[b][i]) { a=up[a][i]; b=up[b][i]; } } return {up[a][0], a, b}; } void modify(int i, int val) { while (i<N) { ft[i]+=val; i+=i&(-i); } } ll get(int i) { int ret=0; while (i) { ret+=ft[i]; i-=i&(-i); } return ret; } int main () { ios::sync_with_stdio(false), cin.tie(0); cin >> n; for (int i=1; i<n; i++) { int u, v; cin >> u >> v; g[u].pb(v); g[v].pb(u); } dfs(1, 0); int q; cin >> q; while (q--) { int a, b, c; cin >> a >> b >> c; array<int, 3> LCA=lca(a, b); pom[LCA[0]].pb({a, b, c}); } for (int i=1; i<=n; i++) dp[i][0]=0, dp[i][1]=0; pii ord[n]; for (int i=1; i<=n; i++) ord[i-1]=make_pair(dep[i], i); sort(ord, ord+n); reverse(ord, ord+n); for (int i=0; i<n; i++) { int x=ord[i].second; for (int u:g[x]) { if (u!=up[x][0]) dp[x][0]+=dp[u][1]; } for (auto z:pom[x]) dp[x][1]=max(dp[x][1], dp[x][0]+get(tin[z.a])+get(tin[z.b])-2*get(tin[x])+z.c); dp[x][1]=max(dp[x][1], dp[x][0]); modify(tin[x], dp[x][0]-dp[x][1]); modify(tout[x], dp[x][1]-dp[x][0]); } cout << max(dp[1][0], dp[1][1]) << '\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...