QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#47396#2228. Bread PittovarischWA 6ms17632kbC++1.5kb2022-09-09 03:12:212022-09-09 03:12:22

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2022-09-09 03:12:22]
  • 评测
  • 测评结果:WA
  • 用时:6ms
  • 内存:17632kb
  • [2022-09-09 03:12:21]
  • 提交

answer

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <cmath>
#include <vector>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <queue>
#include <ctime>
#include <cassert>
#include <complex>
#include <string>
#include <cstring>
#include <chrono>
#include <random>
#include <bitset>
#include <array>

using namespace std;
/* *
 *
 * Too many mind, no mind.
 *
 * */
const int maxn  = 3e5 + 10;
int par[maxn], children[maxn];
vector <int> tree[maxn], leaf[maxn], nodes, idx;
void dfs(int u, int prev = 0) {
	for (int& v: tree[u]) {
		if (v == prev) continue;
		dfs(v, u);
	}
	if (tree[u].size() <= 1) {
		nodes.push_back(prev);
		leaf[prev].push_back(u);
	}
}
int main() {
	ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	//freopen("input.txt", "r", stdin);
	//freopen("output.txt", "w", stdout);
	int n, q; cin >> n >> q;
	for (int i = 1; i < n; i++) {
		cin >> par[i];
		tree[i].push_back(par[i]);
		tree[par[i]].push_back(i);
		children[par[i]]++;

	}
	dfs(0);
	nodes.resize(unique(nodes.begin(), nodes.end()) - nodes.begin());
	idx.assign(nodes.size(), 0);

	bool surface = false;
	for (int i = 0; i < q; i++) {
		int u = nodes[i % nodes.size()];
		cout << (surface ? 0 : leaf[u][idx[u]]) << '\n';
		if (leaf[u][idx[u]] == 0) surface = true;

		idx[u] = (idx[u] + 1) % leaf[u].size();
		if (children[u] == 1) leaf[u][0] = par[leaf[u][0]];
	}
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 5ms
memory: 17500kb

input:

1 1


output:

0

result:

ok single line: '0'

Test #2:

score: -100
Wrong Answer
time: 6ms
memory: 17632kb

input:

2 2
0

output:

1
0

result:

wrong answer 2nd lines differ - expected: '1', found: '0'