QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#712277#9580. 插排串联fsy_juruoWA 1ms6308kbC++17881b2024-11-05 15:08:532024-11-05 15:08:54

Judging History

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

  • [2024-11-05 15:08:54]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:6308kb
  • [2024-11-05 15:08:53]
  • 提交

answer

#include <bits/stdc++.h>
using LL = long long;

const int maxN = 1e5 + 10;

int n, a[maxN];
std::vector<int> v[maxN];

LL tot[maxN], f[maxN], g[maxN];

int cnt = 0;
void dfs(int u) {
	tot[u] = (v[u].empty() ? a[u] : 0);
	for(auto x : v[u]) {
		dfs(x);
		tot[u] += tot[x];
	}
	if(u != 0 && v[u].size()) {
		++cnt;
		g[cnt] = tot[u];
		f[cnt] = a[u];
	}
}
int main() {
	std::ios::sync_with_stdio(false); std::cin.tie(nullptr);
	std::cin >> n;

	a[0] = 2200;
	for(int i = 1; i <= n; i++) {
		int x, y;
		std::cin >> x >> y;
		v[x].emplace_back(i);
		a[i] = y;
	}

	dfs(0);

	std::sort(f + 1, f + cnt + 1);
	std::sort(g + 1, g + cnt + 1);

	bool ok = (tot[0] <= 2200);
	for(int i = 1; i <= cnt; i++) {
		if(g[i] > f[i]) ok = false;
	//	std::cerr << f[i] << " " << g[i] << "\n";
	}

	std::cout << (ok ? "Yes" : "No") << "\n";
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 0
Wrong Answer
time: 1ms
memory: 6308kb

input:

5
0 500
1 700
1 400
2 100
2 200

output:

Yes

result:

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