QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #47410 | #2228. Bread Pit | tovarisch | RE | 5ms | 9640kb | C++ | 1.5kb | 2022-09-09 10:33:34 | 2022-09-09 10:33:35 |
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 = 2e5 + 10;
int children[maxn], order[maxn], par[maxn], ans[maxn];
long long freq[maxn];
vector <int> tree[maxn];
void dfs(int u, int prev = 0) {
for (int& v : tree[u]) {
if (v == prev) continue;
freq[v] = freq[u] * (tree[u].size() - (prev != u));
dfs(v, u);
}
}
void dfs2(int u, int prev = 0, long long pos = 0) {
if (children[u] == 0) {
//cout << u << ' ' << pos << ' ' << freq[u] << ' ' << order[u] << endl;
long long i = pos;
while (i < maxn) {
ans[i] = u;
i += freq[u];
}
}
for (int& v : tree[u]) {
if (v == prev) continue;
long long newpos = pos + order[v] * freq[u];
dfs2(v, u, newpos);
}
}
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];
order[i] = children[par[i]];
children[par[i]]++;
tree[i].push_back(par[i]);
tree[par[i]].push_back(i);
}
freq[0] = 1;
dfs(0);
dfs2(0);
for (int i = 0; i < q; i++) cout << ans[i] << '\n';
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 5ms
memory: 9116kb
input:
1 1
output:
0
result:
ok single line: '0'
Test #2:
score: 0
Accepted
time: 0ms
memory: 9052kb
input:
2 2 0
output:
1 1
result:
ok 2 lines
Test #3:
score: 0
Accepted
time: 2ms
memory: 9052kb
input:
3 3 0 1
output:
2 2 2
result:
ok 3 lines
Test #4:
score: 0
Accepted
time: 1ms
memory: 9056kb
input:
4 4 0 1 1
output:
2 3 2 3
result:
ok 4 lines
Test #5:
score: 0
Accepted
time: 0ms
memory: 8992kb
input:
5 5 0 0 0 1
output:
4 2 3 4 2
result:
ok 5 lines
Test #6:
score: 0
Accepted
time: 5ms
memory: 8928kb
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: 2ms
memory: 9052kb
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: 1ms
memory: 9124kb
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: 2ms
memory: 9016kb
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: 9132kb
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: 9016kb
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: 2ms
memory: 9120kb
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: 9072kb
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: 5ms
memory: 9200kb
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: 0
Accepted
time: 5ms
memory: 9108kb
input:
15 15 0 0 0 3 2 4 6 6 2 5 3 2 2 1
output:
14 10 7 14 9 11 14 12 8 14 13 11 14 10 7
result:
ok 15 lines
Test #16:
score: 0
Accepted
time: 2ms
memory: 9068kb
input:
16 16 0 1 2 1 2 4 1 5 2 6 0 9 10 6 14
output:
3 11 13 11 7 11 8 11 15 11 7 11 12 11 13 11
result:
ok 16 lines
Test #17:
score: 0
Accepted
time: 5ms
memory: 8936kb
input:
17 17 0 1 0 1 2 5 3 3 0 7 10 4 0 5 6 5
output:
15 11 9 13 12 8 9 13 14 11 9 13 12 8 9 13 16
result:
ok 17 lines
Test #18:
score: 0
Accepted
time: 2ms
memory: 8988kb
input:
18 18 0 1 2 0 3 3 4 5 3 9 9 0 1 3 10 5 15
output:
8 7 12 13 7 12 6 7 12 13 7 12 17 7 12 13 7 12
result:
ok 18 lines
Test #19:
score: 0
Accepted
time: 0ms
memory: 8996kb
input:
19 19 0 0 1 2 1 1 0 3 7 4 8 1 9 7 10 10 0 6
output:
11 15 13 17 5 16 14 17 18 15 13 17 12 16 14 17 11 15 13
result:
ok 19 lines
Test #20:
score: 0
Accepted
time: 2ms
memory: 9036kb
input:
20 20 0 1 2 3 1 5 1 3 7 2 9 5 1 9 2 2 4 8 8
output:
17 6 11 13 10 12 14 13 15 6 11 13 16 12 14 13 18 6 11 13
result:
ok 20 lines
Test #21:
score: 0
Accepted
time: 2ms
memory: 9056kb
input:
100 100 0 1 0 1 3 2 5 3 6 9 9 4 1 9 8 10 3 16 1 18 0 0 15 21 17 14 20 7 25 23 21 11 13 11 34 6 2 5 8 26 27 26 3 4 7 39 16 4 32 11 2 48 14 21 1 8 7 30 42 10 27 31 22 2 23 59 9 36 43 56 38 17 40 72 57 18 70 27 27 24 45 72 80 71 84 66 41 15 46 71 89 78 37 62 65 51 9 5 2
output:
87 28 83 63 12 58 94 63 33 29 54 63 19 69 83 63 55 85 94 63 93 91 54 63 44 74 83 63 33 69 94 63 19 98 54 63 55 77 83 63 96 29 94 63 52 69 54 63 33 81 83 63 19 88 94 63 55 82 54 63 64 69 83 63 12 90 94 63 33 91 54 63 19 29 83 63 55 69 94 63 99 98 54 63 44 77 83 63 33 74 94 63 19 69 54 63 55 75 83 63
result:
ok 100 lines
Test #22:
score: 0
Accepted
time: 5ms
memory: 9076kb
input:
1000 1000 0 1 0 1 3 2 2 6 2 4 0 10 12 10 12 0 5 15 10 19 0 21 1 4 22 23 12 12 1 12 20 30 30 3 27 13 28 3 16 1 19 37 30 24 17 5 42 23 14 34 13 0 17 40 54 12 52 14 32 52 56 60 17 9 10 32 4 24 23 8 65 2 2 70 65 17 18 69 7 52 10 58 70 23 29 7 5 42 8 10 68 59 79 17 50 5 90 6 91 61 39 30 81 96 97 82 32 56...
output:
74 855 869 554 851 845 563 685 792 36 543 604 893 294 598 597 685 792 118 271 771 990 800 80 552 685 792 691 647 869 683 661 353 597 685 792 815 323 604 951 717 874 632 685 792 231 608 771 570 800 376 597 685 792 643 559 869 966 463 600 563 685 792 319 833 604 683 294 221 597 685 792 137 327 771 554...
result:
ok 1000 lines
Test #23:
score: 0
Accepted
time: 4ms
memory: 9640kb
input:
10000 10000 0 1 2 3 1 0 3 7 3 5 1 7 8 1 4 10 2 2 10 14 14 20 22 20 17 20 13 20 0 6 3 18 32 17 33 8 8 14 8 17 10 17 13 4 19 29 9 14 9 45 22 51 31 50 52 19 52 31 37 32 37 53 18 14 28 24 7 64 32 33 53 42 56 16 44 4 35 65 64 79 17 71 72 38 4 52 32 71 1 47 49 15 92 3 78 57 34 40 46 72 63 44 93 93 91 12 6...
output:
2900 763 2158 1739 5439 9265 5427 7984 4769 1621 3948 5439 9265 5427 705 6826 9518 7178 5439 9265 5427 1540 6552 6257 4031 5439 9265 5427 3776 3775 8991 5142 5439 9265 5427 9175 3149 7781 7178 5439 9265 5427 9243 6215 8620 4626 5439 9265 5427 4359 7313 4228 3948 5439 9265 5427 3856 6778 1404 7178 54...
result:
ok 10000 lines
Test #24:
score: -100
Runtime Error
input:
100000 100000 0 0 2 2 0 3 0 3 2 6 6 7 10 0 9 4 7 4 5 6 13 21 5 19 22 20 0 22 14 4 15 23 4 2 5 6 36 25 32 30 5 6 32 14 37 17 40 1 32 41 18 13 38 27 20 38 35 12 31 28 37 44 56 51 53 51 61 43 17 46 51 57 3 52 62 64 36 53 59 19 16 26 60 27 61 57 78 15 37 84 34 74 88 33 69 61 9 18 40 0 68 30 51 66 92 79 ...