Submission #128200

#TimeUsernameProblemLanguageResultExecution timeMemory
128200mirbek01Election Campaign (JOI15_election_campaign)C++11
20 / 100
1061 ms30712 KiB
# include <bits/stdc++.h> using namespace std; const int N = 1e5 + 2; int n, m, a[N], b[N], c[N], dp[N]; int up[17][N], tin[N], tout[N], timer, ver[N]; vector <int> g[N], qe[N]; void dfs(int v, int pr){ tin[v] = ++ timer; ver[timer] = v; up[0][v] = pr; for(int i = 1; i <= 16; i ++) up[i][v] = up[i - 1][up[i - 1][v]]; for(int to : g[v]){ if(to == pr) continue; dfs(to, v); } tout[v] = timer; } 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 i = 16; i >= 0; i --){ if(!upper(up[i][a], b)) a = up[i][a]; } return up[0][a]; } void calc(int v, int pr){ for(int to : g[v]){ if(to == pr) continue; calc(to, v); } long long sum = 0; for(int to : g[v]){ if(to == pr) continue; sum += dp[to]; } dp[v] = sum; for(int i = 0; i < qe[v].size(); i ++){ int id = qe[v][i]; int ret = c[id]; int vr = a[id]; while(vr != v){ if(up[0][vr] != v){ for(int to : g[ up[0][vr] ]){ if(to == up[1][vr] || to == vr) continue; ret += dp[to]; } } vr = up[0][vr]; } vr = b[id]; while(vr != v){ if(up[0][vr] != v){ for(int to : g[ up[0][vr] ]){ if(to == up[1][vr] || to == vr) continue; ret += dp[to]; } } vr = up[0][vr]; } for(int to : g[v]){ if(to == pr || upper(to, a[id]) || upper(to, b[id])) continue; ret += dp[to]; } if(v != a[id]){ for(int to : g[ a[id] ]){ if(to == up[0][ a[id] ]) continue; ret += dp[to]; } } if(v != b[id]){ for(int to : g[ b[id] ]){ if(to == up[0][ b[id] ]) continue; ret += dp[to]; } } dp[v] = max(dp[v], ret); } } int main(){ scanf("%d", &n); for(int i = 1; i < n; i ++){ int u, v; scanf("%d %d", &u, &v); g[u].push_back(v); g[v].push_back(u); } dfs(1, 1); scanf("%d", &m); for(int i = 1; i <= m; i ++){ scanf("%d %d %d", a+i, b+i, c+i); qe[ lca(a[i], b[i]) ].push_back(i); } calc(1, 1); cout << dp[1] << endl; }

Compilation message (stderr)

election_campaign.cpp: In function 'void calc(int, int)':
election_campaign.cpp:54:24: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
       for(int i = 0; i < qe[v].size(); i ++){
                      ~~^~~~~~~~~~~~~~
election_campaign.cpp: In function 'int main()':
election_campaign.cpp:103:12: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
       scanf("%d", &n);
       ~~~~~^~~~~~~~~~
election_campaign.cpp:107:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
             scanf("%d %d", &u, &v);
             ~~~~~^~~~~~~~~~~~~~~~~
election_campaign.cpp:114:12: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
       scanf("%d", &m);
       ~~~~~^~~~~~~~~~
election_campaign.cpp:117:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
             scanf("%d %d %d", a+i, b+i, c+i);
             ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
#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...