oj.uz

Submission #753459

# Submission time Handle Problem Language Result Execution time Memory
753459 2023-06-05T09:10:54 Z lukameladze Arboras (RMI20_arboras) C++14
24 / 100
 5000 ms 19196 KB 
# include <bits/stdc++.h>
using namespace std;
#define f first
#define s second
#define int long long
#define pii pair <int, int>
#define pb push_back
const int N = 3e5 + 5, mod = 1e9 + 7;
//int n,sz[N],mx,bigchild[N],in[N],out[N],p_[N],chain[N],tin,dep[N],to_par[N],x[N];
//vector <pii> v[N];
int n,dep[N],to_par[N],ans,p_[N],is[N];
pii mx[N][2], pot[2];
vector <pii> v[N];
void dfs(int a, int p) {
	dep[a] = dep[p] + to_par[a];
	vector <pii> vec;
	for (pii sth : v[a]) {
		int to = sth.f, c = sth.s;
		if (to == p) continue;
		dfs(to, a);
		vec.pb({mx[to][0].f + c, to});
	}
	sort(vec.rbegin(), vec.rend());
	if (vec.size() > 0) mx[a][1] = mx[a][0], mx[a][0] = vec[0];
	if (vec.size() > 1) mx[a][1] = vec[1];
	ans += mx[a][0].f + mx[a][1].f;
	ans %= mod;
}
main() {
    std::ios_base::sync_with_stdio(false),cin.tie(0),cout.tie(0);
    cin>>n;
    for (int i = 2; i <= n; i++) {
        cin>>p_[i]; p_[i]++;
    }
    for (int i = 2; i <= n; i++) {
        int c;
        cin>>c;
        to_par[i] = c;
        v[p_[i]].pb({i, c});
        //v[i].pb({p_[i], c});
    }
    for (int i = 1; i <= n ;i++) {
    	mx[i][0] = {0, i};
    	mx[i][1] = {0, 0};
	}
    dfs(1, 0);
	cout<<ans<<"\n";
    int q; cin>>q;
    while (q--) {
    	int vert, to_add;
    	cin>>vert>>to_add; vert++;
    	 int cur = vert;
//    	pot[1] = mx[vert][1]; pot[1].f += to_add;
		int best = mx[cur][0].f + to_add;
		while (cur != 1) {
			is[p_[cur]] = mx[cur][0].f + to_par[cur];
			cur = p_[cur];
		} 
		cur = vert;
    	while (cur != 1) {
    		pot[0].f = is[p_[cur]]; pot[0].s = cur;
    		best += to_par[cur];
    		pot[0].f = max(pot[0].f, best);
    		ans -= (mx[p_[cur]][0].f + mx[p_[cur]][1].f) % mod;
    		ans += mod;
    		ans %= mod;
			for (int j = 0; j <= 0; j++) {
				if (pot[j].s != 0) {
					if (mx[p_[cur]][0].f <= pot[j].f) {
						if (cur == mx[p_[cur]][0].s) mx[p_[cur]][0] = pot[j];
						else mx[p_[cur]][1] = mx[p_[cur]][0], mx[p_[cur]][0] = pot[j];
						continue;
					}
					if (mx[p_[cur]][1].f <= pot[j].f) {
						if (cur == mx[p_[cur]][0].s) continue;
						mx[p_[cur]][1] = pot[j]; 
					}
				}
			}
			ans += (mx[p_[cur]][0].f + mx[p_[cur]][1].f) % mod;
			ans %= mod;
    		cur = p_[cur];
		}
		to_par[vert] += to_add;
		cout<<ans<<"\n";
	}
}

Compilation message

arboras.cpp:29:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   29 | main() {
      | ^~~~

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 7508 KB Output is correct
2 Correct 10 ms 7508 KB Output is correct
3 Correct 6 ms 7520 KB Output is correct

Subtask #2
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 94 ms 17100 KB Output is correct
2 Correct 123 ms 18084 KB Output is correct
3 Correct 91 ms 18116 KB Output is correct

Subtask #3
0 / 31.0

# Verdict Execution time Memory Grader output
1 Execution timed out 5041 ms 19196 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 7508 KB Output is correct
2 Correct 10 ms 7508 KB Output is correct
3 Correct 6 ms 7520 KB Output is correct
4 Correct 94 ms 17100 KB Output is correct
5 Correct 123 ms 18084 KB Output is correct
6 Correct 91 ms 18116 KB Output is correct
7 Execution timed out 5041 ms 19196 KB Time limit exceeded
8 Halted 0 ms 0 KB -