Submission #478749

#TimeUsernameProblemLanguageResultExecution timeMemory
478749stefantagaArboras (RMI20_arboras)C++14
24 / 100
5043 ms9576 KiB
#include <bits/stdc++.h> #define MOD 1000000007 using namespace std; pair <int,int> ceau[100005]; long long val[100005],cost[100005],lung[100005]; void haide(int poz) { val[poz]=lung[ceau[poz].first]+cost[ceau[poz].first]+lung[ceau[poz].second]+cost[ceau[poz].second]; } long long sum,inainte; void updateaza(int poz,int nod) { if (ceau[poz].first==nod) { inainte=val[poz]; haide(poz); sum=(sum+(val[poz]%MOD)-(inainte%MOD)+MOD)%MOD; } else if (ceau[poz].second==nod) { if (lung[nod]+cost[nod]>lung[ceau[poz].first]+cost[ceau[poz].first]) { ceau[poz].second=ceau[poz].first; ceau[poz].first=nod; } inainte=val[poz]; haide(poz); sum=(sum+(val[poz]%MOD)-(inainte%MOD)+MOD)%MOD; } else { if (lung[nod]+cost[nod]>lung[ceau[poz].first]+cost[ceau[poz].first]) { ceau[poz].second=ceau[poz].first; ceau[poz].first=nod; } else { if (lung[nod]+cost[nod]>lung[ceau[poz].second]+cost[ceau[poz].second]) { ceau[poz].second=nod; } } inainte=val[poz]; haide(poz); sum=(sum+(val[poz]%MOD)-(inainte%MOD)+MOD)%MOD; } lung[poz]=max(lung[poz],lung[nod]+cost[nod]); } vector <int> v[100005]; int loc; void dfs(int x) { for (int i=0;i<v[x].size();i++) { dfs(v[x][i]); loc=v[x][i]; updateaza(x,loc); } } int n,i,tata[100005]; int main() { ios_base :: sync_with_stdio(false); cin.tie(0); #ifdef HOME ifstream cin("date.in"); ofstream cout("date.out"); #endif // HOME cin>>n; for (i=2;i<=n;i++) { cin>>tata[i]; tata[i]++; v[tata[i]].push_back(i); } for (i=2;i<=n;i++) { cin>>cost[i]; } dfs(1); cout<<sum<<'\n'; int q,x,y; cin>>q; for (i=1;i<=q;i++) { cin>>x>>y; x++; cost[x]+=y; while (x!=1) { updateaza(tata[x],x); x=tata[x]; } cout<<sum<<'\n'; } return 0; }

Compilation message (stderr)

arboras.cpp: In function 'void dfs(int)':
arboras.cpp:55:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   55 |     for (int i=0;i<v[x].size();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...