oj.uz

Submission #645214

# Submission time Handle Problem Language Result Execution time Memory
645214 2022-09-26T12:49:35 Z TimDee Arboras (RMI20_arboras) C++17
0 / 100
 5000 ms 9644 KB 
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define forn(i,n) for (int i=0; i<n; ++i)
#define pi pair<int,int>
#define ppi pair<int,pi>
#define f first
#define s second
const int mod = 1e9+7;

vector<vector<int>> adj(1e5+3);
vector<int> d(1e5+3,0);

ppi dfs(int u, int p) {
	ppi ret={0,{0,0}};
	for (auto v:adj[u]) {
		if (v==p) continue;
		ppi k=dfs(v,u);
		ret.f+=k.f;
		ret.s.f=max(ret.s.f,k.s.s+d[v]);
		if (ret.s.f>ret.s.s) swap(ret.s.f,ret.s.s);

	}
	ret.f+=ret.s.f+ret.s.s;
	return ret;
}

void solve() {
	int n; cin>>n;
	forn(i,n-1) {
		int v; cin>>v;
		adj[v].push_back(i+1);
	}
	forn(i,n-1) cin>>d[i+1];
	cout<<dfs(0,-1).f<<'\n';

	int Q; cin>>Q;
	forn(q,Q) {
		int i,x; cin>>i>>x;
		d[i]+=x;
		int ans=0;
		cout<<dfs(0,-1).f<<'\n';
	}
}

int32_t main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	solve();
	return 0;
}

Compilation message

arboras.cpp: In function 'void solve()':
arboras.cpp:41:7: warning: unused variable 'ans' [-Wunused-variable]
   41 |   int ans=0;
      |       ^~~

Subtask #1
0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 17 ms 3540 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 13.0

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

Subtask #3
0 / 31.0

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

Subtask #4
0 / 45.0

# Verdict Execution time Memory Grader output
1 Incorrect 17 ms 3540 KB Output isn't correct
2 Halted 0 ms 0 KB -