제출 #36010

#제출 시각아이디문제언어결과실행 시간메모리
36010ngkan146Election Campaign (JOI15_election_campaign)C++98
10 / 100
413 ms40252 KiB
#include <bits/stdc++.h> #define ll long long using namespace std; struct query{ int a,b,val; query(int a=0,int b=0,int val=0): a(a), b(b), val(val) {} }; int n,m,lv[100005], beg[100005], fin[100005], p[100005][20], ___time; vector <int> G[100005]; vector <query> Q[100005]; void dfs(int u){ for(int k=1;k<20;k++) p[u][k] = p[p[u][k-1]][k-1]; beg[u] = ++___time; for(int i=0;i<(int)G[u].size();i++){ int v = G[u][i]; if (v == p[u][0]) continue; p[v][0] = u; lv[v] = lv[u]+1; dfs(v); } fin[u] = ___time; } int lca(int x,int y){ for(int k=19;k>=0;k--) if (lv[p[x][k]] >= lv[y]) x = p[x][k]; for(int k=19;k>=0;k--) if (lv[p[y][k]] >= lv[x]) y = p[y][k]; if (x == y) return x; for(int k=19;k>=0;k--) if (p[x][k] != p[y][k]) x = p[x][k], y = p[y][k]; return p[x][0]; } ll seg[400005], lazy[400005]; void _lazy(int id,int l,int r){ seg[id] += lazy[id] * (r - l + 1); if (l != r){ lazy[2*id] += lazy[id]; lazy[2*id+1] += lazy[id]; } lazy[id] = 0; } void seg_upd(int id,int l,int r,int u,int v,ll val){ _lazy(id,l,r); if (r < u || v < l) return; if (u <= l && r <= v){ lazy[id] += val; _lazy(id,l,r); return; } seg_upd(2*id, l, (l+r)/2, u, v, val); seg_upd(2*id+1, (l+r)/2+1, r, u, v, val); seg[id] = seg[2*id] + seg[2*id+1]; } ll seg_get(int id,int l,int r,int pos){ if (r < pos || pos < l) return 0; if (l == r) return seg[id]; return seg_get(2*id, l, (l+r)/2, pos) + seg_get(2*id+1, (l+r)/2+1, r, pos); } ll dp[100005]; ll get_decendant(int x,int y){ int l = 0, r = G[x].size(); while(l+1 < r){ int mid = (l+r)/2; int z = G[x][mid]; if (beg[y] < beg[z]) r = mid; else l = mid; } return G[x][l]; } void solve(int u){ ll sum = 0; //cout << u << ' ' << p[u][0] << endl; for(int i=0;i<(int)G[u].size();i++){ if (G[u][i] != p[u][0]) solve(G[u][i]), sum += dp[G[u][i]]; } dp[u] = sum; for(int id=0;id<(int)Q[u].size();id++){ int a = Q[u][id].a; int b = Q[u][id].b; int val = Q[u][id].val; //cout << "Q" << u << ' ' << a << ' ' << b << endl; if (a == u) dp[u] = max(dp[u], seg_get(1,1,n,beg[b]) + sum - dp[get_decendant(u,b)] + val); else if (b == u) dp[u] = max(dp[u], seg_get(1,1,n,beg[a]) + sum - dp[get_decendant(u,a)] + val); else dp[u] = max(dp[u], sum + seg_get(1,1,n,beg[a]) + seg_get(1,1,n,beg[b]) - dp[get_decendant(u,a)] - dp[get_decendant(u,b)] + val); } for(int i=0;i<(int)G[u].size();i++){ int v = G[u][i]; if (v == p[u][0]) continue; seg_upd(1,1,n,beg[v],fin[v], sum - dp[v]); } seg_upd(1,1,n,beg[u],beg[u], sum); //cout << "res " << u << ' ' << dp[u] << endl; } bool cmp(int x,int y){ return beg[x] < beg[y]; } int main(){ scanf("%d",&n); for(int i=1;i<n;i++){ int x,y; scanf("%d %d",&x,&y); G[x].push_back(y); G[y].push_back(x); } lv[1] = 1; dfs(1); scanf("%d",&m); for(int i=1;i<=m;i++){ int a,b,val; scanf("%d %d %d",&a,&b,&val); Q[lca(a,b)].push_back(query(a,b,val)); } for(int i=1;i<=n;i++) sort(G[i].begin(), G[i].end(), cmp); solve(1); cout << dp[1]; } /* 7 3 4 6 5 2 7 1 5 7 5 4 5 5 4 3 10 5 6 5 2 6 9 7 2 2 1 3 8 */

컴파일 시 표준 에러 (stderr) 메시지

election_campaign.cpp: In function 'int main()':
election_campaign.cpp:103:16: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d",&n);
                ^
election_campaign.cpp:106:23: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d",&x,&y);
                       ^
election_campaign.cpp:112:16: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d",&m);
                ^
election_campaign.cpp:115:31: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d %d",&a,&b,&val);
                               ^
#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...