QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#47397 | #2228. Bread Pit | tovarisch | RE | 0ms | 0kb | C++ | 1.5kb | 2022-09-09 03:14:20 | 2022-09-09 03:14:23 |
Judging History
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 (u && 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;
}
详细
Test #1:
score: 0
Runtime Error
input:
1 1