제출 #398527

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
398527		model_code	Arboras (RMI20_arboras)	C++17	13 / 100	83 ms	12540 KiB

arboras

/**
* user:  dossi-74c
* fname: Tommaso
* lname: Dossi
* task:  Arboras
* score: 13.0
* date:  2020-12-04 11:54:27.709767
*/
#include<bits/stdc++.h>
#pragma gcc optimize("O3")
using namespace std;
#define pb push_back
#define mp make_pair
#define fi first
#define se second
typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
const int MAXN = 100010;
const ll MOD = 1000000007;
vi adj[MAXN];
ll p[MAXN],w[MAXN];
ll m1[MAXN],m2[MAXN];
ll pr1[MAXN],pr2[MAXN];
ll cnt[MAXN];
int Q,N,a,b;
void dfs(int pp){
	for(auto a: adj[pp]){
		dfs(a);
		if(m1[a]+w[a]>m2[pp]){
			m2[pp] = m1[a]+w[a];
			pr2[pp] = a;
		}
		if(m2[pp]>m1[pp]){
			swap(m1[pp],m2[pp]);
			swap(pr1[pp],pr2[pp]);
		}
	}
	cnt[pr2[pp]] = 1;
	cnt[pr1[pp]] = cnt[pp]+1;
}
ll ans;
int main(){
	cin.tie(0);
	ios_base::sync_with_stdio(NULL);
	cin >> N;
	for(int i = 1; i < N; i++){
		cin >> p[i];
		adj[p[i]].pb(i);
	}
	for(int i = 1; i < N; i++){
		cin >> w[i];
	}
	dfs(0);
	for(int i = 0; i < N; i++){
		ans+=m1[i]+m2[i]; ans%=MOD;
	}
	cout << ans << "\n";
	cin >> Q;
	int k,pp;
	while(Q--){
		cin >> a >> b;
		w[a]+=b; 
		k = 0;
		while(a!=0){
			if(k > 50)break;
			k++;
			pp = p[a];
			if(m1[a]+w[a]>m1[pp]){
				if(pr1[pp]!=a){
					ans+=w[a]+m1[a] - m2[pp];
					ans%MOD;
					m2[pp] = m1[pp];
					pr2[pp] = pr1[pp];
				
				}else{
					ans+=w[a]+m1[a]-m1[pp];		
					ans%=MOD;			
				}
				m1[pp] = w[a] + m1[a];
				pr1[pp] = a;
			}else if(m1[a] + w[a] > m2[pp] && pr1[pp]!= a){
				ans += m1[a] + w[a] - m2[pp];
				ans%MOD;

				m2[pp] = m1[a] + w[a];
				pr2[pp] = a;
			}else break;
			
			a = pp;
		}
		if(k > 50)ans+=cnt[a];
		ans%=MOD;
		cout << ans << "\n";
	}
	/*while(Q--){
		cin >> a >> b;
		if(a == 0){
			cout << ans <<"\n";
			continue;
		}
		ans += cnt[a];
		ans%=MOD;
		cout << ans <<"\n";
	}*/
	return 0;
}

컴파일 시 표준 에러 (stderr) 메시지

arboras.cpp:10: warning: ignoring #pragma gcc optimize [-Wunknown-pragmas]
   10 | #pragma gcc optimize("O3")
      | 
arboras.cpp: In function 'int main()':
arboras.cpp:74:9: warning: statement has no effect [-Wunused-value]
   74 |      ans%MOD;
      |      ~~~^~~~
arboras.cpp:86:8: warning: statement has no effect [-Wunused-value]
   86 |     ans%MOD;
      |     ~~~^~~~

• Subtask 1: 0 / 11
• Subtask 2: 13 / 13
• Subtask 3: 0 / 31
• Subtask 4: 0 / 45