QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#715633#9580. 插排串联carboxylBaseWA 1ms3712kbC++231.2kb2024-11-06 12:49:452024-11-06 12:49:47

Judging History

你现在查看的是最新测评结果

  • [2024-11-06 12:49:47]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:3712kb
  • [2024-11-06 12:49:45]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define int long long

int n;
vector<int> a;
vector<vector<int>> b;
vector<int> c;
vector<int> q;
void dfs(int u,int f){
	for (auto v:b[u]){
		if (v == f){
			continue;
		}
		dfs(v,u);
		c[u] += c[v];
	}
	if (b[u].size()==0){
		c[u] += a[u];
	}else{
		if (c[u] > a[u] && u != 0){
			q.push_back(u);
		}
	}
	// cout << u << " " << c[u] << endl;
	return;
}
void solve(){
	cin >> n;
	a.resize(n+1,0);
	b.resize(n+1);
	c.resize(n+1,0);
	a[0] = 0x3f3f3f3f3f3f3f;
	for (int i = 1;i<n+1;i++){
		int f;
		cin >> f;
		b[f].push_back(i);
		cin >> a[i];
	}
	dfs(0,0);
	// cout << q.size() << endl;
	if (q.size() > 1){
		cout << "NO" <<endl;
		return;
	}else if (q.size() == 0){
		cout<<"YES"<<endl;
	}else{
		for (int i = 1;i<n+1;i++){
			if (b[i].size() > 1 && a[i] >= c[q[0]] && 
			a[q[0]] >= c[i]){
				cout << "YES"<<endl;
				return;
			}
		}
		cout << "NO" <<endl;
	} 
    return;
}

signed main(){
    // freopen("input.txt","r",stdin);
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    int _ = 1;
    while (_--){
        solve();
    }
    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 1ms
memory: 3712kb

input:

5
0 500
1 700
1 400
2 100
2 200

output:

YES

result:

ok single line: 'YES'

Test #2:

score: 0
Accepted
time: 0ms
memory: 3588kb

input:

5
0 500
1 700
1 400
2 100
2 300

output:

NO

result:

ok single line: 'NO'

Test #3:

score: 0
Accepted
time: 0ms
memory: 3668kb

input:

4
0 1000
1 800
1 500
2 300

output:

YES

result:

ok single line: 'YES'

Test #4:

score: -100
Wrong Answer
time: 0ms
memory: 3648kb

input:

3
0 1000000000
0 1000000000
0 147483647

output:

YES

result:

wrong answer 1st lines differ - expected: 'NO', found: 'YES'