oj.uz

답안 #753453

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
753453 2023-06-05T08:57:46 Z lukameladze Arboras (RMI20_arboras) C++14
0 / 100
 5000 ms 24084 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({dep[to], to});
	}
	sort(vec.rbegin(), vec.rend());
	if (vec.size() > 0) mx[a][0] = vec[0];
	if (vec.size() > 1) mx[a][1] = vec[1];
	ans += mx[a][0].f + mx[a][1].f;
}
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]; 
					}
				}
			}
//			cout<<cur<<" --- > "<<mx[cur][0].f<<" "<<mx[cur][0].s<<"          "<<mx[cur][1].f<<" "<<mx[cur][1].s<<"\n";
			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: In function 'void dfs(long long int, long long int)':
arboras.cpp:18:19: warning: unused variable 'c' [-Wunused-variable]
   18 |   int to = sth.f, c = sth.s;
      |                   ^
arboras.cpp: At global scope:
arboras.cpp:28:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   28 | main() {
      | ^~~~

Subtask #1
0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 6 ms 7568 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 112 ms 21736 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 31.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 5035 ms 24084 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 45.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 6 ms 7568 KB Output isn't correct
2 Halted 0 ms 0 KB -