QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #47403 | #2228. Bread Pit | tovarisch | WA | 8ms | 17704kb | C++ | 1.5kb | 2022-09-09 05:47:52 | 2022-09-09 05:47:55 |
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 root = 0, par[maxn], children[maxn], idx[maxn];
vector <int> tree[maxn], leaf[maxn], nodes;
void dfs(int u, int prev = 0, int f = 0) {
if (children[root] == 1 && par[u] == root) root = u;
if (children[u] == 0) {
nodes.push_back(f == root ? u : f);
leaf[f == root ? u : f].push_back(u);
}
//cout << u << ' ' << f << endl;
if (children[u] > 1) f = u;
for (int& v: tree[u]) {
if (v == prev) continue;
dfs(v, u, u == 0 ? v : f);
}
}
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());
for (int i = 0; i < q; i++) {
int u = nodes[i % nodes.size()];
cout << leaf[u][idx[u]] << '\n';
idx[u] = (idx[u] + 1) % leaf[u].size();
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 4ms
memory: 17612kb
input:
1 1
output:
0
result:
ok single line: '0'
Test #2:
score: 0
Accepted
time: 5ms
memory: 17700kb
input:
2 2 0
output:
1 1
result:
ok 2 lines
Test #3:
score: 0
Accepted
time: 8ms
memory: 17556kb
input:
3 3 0 1
output:
2 2 2
result:
ok 3 lines
Test #4:
score: 0
Accepted
time: 4ms
memory: 17688kb
input:
4 4 0 1 1
output:
2 3 2 3
result:
ok 4 lines
Test #5:
score: 0
Accepted
time: 4ms
memory: 17688kb
input:
5 5 0 0 0 1
output:
4 2 3 4 2
result:
ok 5 lines
Test #6:
score: 0
Accepted
time: 2ms
memory: 17624kb
input:
6 6 0 1 2 3 3
output:
4 5 4 5 4 5
result:
ok 6 lines
Test #7:
score: 0
Accepted
time: 7ms
memory: 17696kb
input:
7 7 0 0 0 0 1 5
output:
6 2 3 4 6 2 3
result:
ok 7 lines
Test #8:
score: 0
Accepted
time: 2ms
memory: 17668kb
input:
8 8 0 1 0 2 0 2 6
output:
4 3 5 7 3 5 4 3
result:
ok 8 lines
Test #9:
score: 0
Accepted
time: 3ms
memory: 17632kb
input:
9 9 0 1 2 2 2 0 3 7
output:
8 6 4 6 5 6 8 6 4
result:
ok 9 lines
Test #10:
score: 0
Accepted
time: 2ms
memory: 17704kb
input:
10 10 0 0 1 2 4 3 5 7 5
output:
6 8 6 9 6 8 6 9 6 8
result:
ok 10 lines
Test #11:
score: 0
Accepted
time: 2ms
memory: 17704kb
input:
11 11 0 0 2 3 0 5 5 3 8 6
output:
1 4 10 1 9 7 1 4 10 1 9
result:
ok 11 lines
Test #12:
score: 0
Accepted
time: 6ms
memory: 17632kb
input:
12 12 0 0 2 0 1 3 6 4 6 6 9
output:
5 7 8 5 11 8 5 10 8 5 7 8
result:
ok 12 lines
Test #13:
score: 0
Accepted
time: 1ms
memory: 17628kb
input:
13 13 0 1 1 1 4 3 2 1 2 7 1 8
output:
10 6 5 12 11 9 6 5 12 11 10 6 5
result:
ok 13 lines
Test #14:
score: 0
Accepted
time: 2ms
memory: 17664kb
input:
14 14 0 0 1 0 1 2 4 0 6 1 3 7 10
output:
11 9 12 8 5 9 12 8 13 9 12 8 11 9
result:
ok 14 lines
Test #15:
score: -100
Wrong Answer
time: 2ms
memory: 17632kb
input:
15 15 0 0 0 3 2 4 6 6 2 5 3 2 2 1
output:
14 10 7 11 14 9 8 11 14 12 7 11 14 13 8
result:
wrong answer 4th lines differ - expected: '14', found: '11'