Submission #444693

#TimeUsernameProblemLanguageResultExecution timeMemory
444693NintsiChkhaidzeElection Campaign (JOI15_election_campaign)C++14
100 / 100
536 ms48948 KiB
#include <bits/stdc++.h> #define pb push_back #define s second #define f first #define ll long long #define pii pair<int,int> #define left (node<<1),l,((l+r)>>1) #define right ((node<<1)|1),((l+r)>>1) + 1,r #define int ll using namespace std; const int N = 100005; int cnt,a[N],d[25][N],dep[N],dp[N],in[N],out[N],fen[N]; vector <int> v[N]; set <pii> st; vector <pair<pii,int> > vec[N]; void dfs(int x,int par){ dep[x] = dep[par] + 1; in[x] = ++cnt; d[0][x] = par; for (int j = 0; j < v[x].size(); j++){ int to = v[x][j]; if (to != par) dfs(to,x); } out[x] = cnt; } void upd(int ind,int val){ while(ind <= N){ fen[ind] += val; ind += (ind&(-ind)); } } int get(int ind){ int s=0; while(ind){ s += fen[ind]; ind -= (ind&(-ind)); } return s; } void solve(int x){ int S = 0; for (int j = 0; j < v[x].size(); j++){ int to = v[x][j]; if (to == d[0][x]) continue; solve(to); S += dp[to]; } dp[x] = S; upd(in[x], S); upd(in[x] + 1,-S); st.clear(); st.insert({N,0}); for (int j = 0; j < v[x].size(); j++){ int to = v[x][j]; if (to == d[0][x]) continue; st.insert({in[to],dp[to]}); } for (int j = 0; j < vec[x].size(); j++){ int l = vec[x][j].f.f,r = vec[x][j].f.s; int s = vec[x][j].s + S; set <pii> :: iterator it; if (l != x){ s += get(in[l]); it = st.lower_bound({in[l],1e18}); it--; s -= (it->s); } if (r != x){ s += get(in[r]); it = st.lower_bound({in[r],1e18}); it--; s -= (it->s); } dp[x] = max(dp[x],s); } for (int j = 0; j < v[x].size(); j++){ int to = v[x][j]; if (to == d[0][x]) continue; S -= dp[to]; upd(in[to], S); upd(out[to] + 1,-S); S += dp[to]; } } int lca(int x,int y){ if (dep[x] > dep[y]) swap(x,y); for (int j = 20; j >= 0; j--) if (dep[d[j][y]] >= dep[x]) y = d[j][y]; if (x == y) return x; for (int j = 20; j >= 0; j--) if (d[j][x] != d[j][y]) x = d[j][x],y = d[j][y]; return d[0][x]; } main (){ ios_base::sync_with_stdio(0),cin.tie(NULL),cout.tie(NULL); int n; cin>>n; for (int i =1; i <n;i++){ int a,b; cin>>a>>b; v[a].pb(b),v[b].pb(a); } dfs(1,1); for (int i = 1; i <= 20; i++) for (int j = 1; j <= n; j++) d[i][j] = d[i - 1][d[i - 1][j]]; int q; cin>>q; while(q--){ int x,y,z; cin>>x>>y>>z; int c = lca(x,y); vec[c].pb({{x,y},z}); } solve(1); cout<<dp[1]; }

Compilation message (stderr)

election_campaign.cpp: In function 'void dfs(long long int, long long int)':
election_campaign.cpp:20:23: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   20 |     for (int j = 0; j < v[x].size(); j++){
      |                     ~~^~~~~~~~~~~~~
election_campaign.cpp: In function 'void solve(long long int)':
election_campaign.cpp:42:23: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   42 |     for (int j = 0; j < v[x].size(); j++){
      |                     ~~^~~~~~~~~~~~~
election_campaign.cpp:53:23: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   53 |     for (int j = 0; j < v[x].size(); j++){
      |                     ~~^~~~~~~~~~~~~
election_campaign.cpp:59:23: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<std::pair<long long int, long long int>, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   59 |     for (int j = 0; j < vec[x].size(); j++){
      |                     ~~^~~~~~~~~~~~~~~
election_campaign.cpp:81:23: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   81 |     for (int j = 0; j < v[x].size(); j++){
      |                     ~~^~~~~~~~~~~~~
election_campaign.cpp: At global scope:
election_campaign.cpp:103:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
  103 | main (){
      | ^~~~
#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...