Task: | Company Queries II |
Sender: | Rasse |
Submission time: | 2024-10-16 20:41:41 +0300 |
Language: | C++ (C++11) |
Status: | READY |
Result: | WRONG ANSWER |
test | verdict | time | |
---|---|---|---|
#1 | WRONG ANSWER | 0.00 s | details |
#2 | ACCEPTED | 0.00 s | details |
#3 | ACCEPTED | 0.00 s | details |
#4 | WRONG ANSWER | 0.00 s | details |
#5 | WRONG ANSWER | 0.00 s | details |
#6 | TIME LIMIT EXCEEDED | -- | details |
#7 | ACCEPTED | 0.64 s | details |
#8 | WRONG ANSWER | 0.85 s | details |
#9 | TIME LIMIT EXCEEDED | -- | details |
#10 | TIME LIMIT EXCEEDED | -- | details |
#11 | ACCEPTED | 0.00 s | details |
#12 | TIME LIMIT EXCEEDED | -- | details |
Compiler report
input/code.cpp: In function 'void solve()': input/code.cpp:59:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare] 59 | for (int a = 0; a < parents.size(); a++) | ~~^~~~~~~~~~~~~~~~
Code
#include <iostream>#include <vector>#include <string>#include <algorithm>#include <numeric>#include <unordered_map>#include <queue>#include <climits>#include <cmath>//#define int long longusing namespace std;vector<int> deepness;vector<vector<int>> adj;vector<vector<int>> parents;void calc(int i, int deep){deepness[i] = deep;for (auto& num : adj[i]){calc(num, deep + 1);}}int getParent(int a, int i){int loopIdx = 0;while (i > 0){if ((i & 1) == 1)a = parents[a][loopIdx];loopIdx++;i >>= 1;}return a;}void solve(){int n, q;cin >> n >> q;adj = vector<vector<int>>(n, vector<int>());parents = vector<vector<int>>(n, vector<int>(40));deepness = vector<int>(n);parents[0][0] = 0;for (int i = 1; i < n; i++){int a;cin >> a;a--;adj[a].push_back(i);parents[i][0] = a;}for (int i = 1; i < 40; i++){for (int a = 0; a < parents.size(); a++)parents[a][i] = parents[parents[a][i-1]][i-1];}calc(0, 0);for (int i = 0; i < q; i++){int a, b;cin >> a >> b;a--; b--;if (deepness[a] > deepness[b])b = getParent(b, deepness[a] - deepness[b]);elsea = getParent(a, deepness[b] - deepness[a]);while (a != b){a = parents[a][0];b = parents[b][0];}cout << a+1 << '\n';}}signed main(){//ios::sync_with_stdio(0);//cin.tie(0);int t = 1;//cin >> t;for (int i = 0; i < t; i++)solve();return 0;}
Test details
Test 1
Verdict: WRONG ANSWER
input |
---|
10 10 1 2 3 4 5 6 7 8 9 6 9 8 10 10 3 ... |
correct output |
---|
6 8 3 1 8 ... |
user output |
---|
1 1 1 1 1 ... |
Test 2
Verdict: ACCEPTED
input |
---|
10 10 1 1 1 1 1 1 1 1 1 1 7 3 4 4 1 ... |
correct output |
---|
1 1 1 1 1 ... |
user output |
---|
1 1 1 1 1 ... |
Test 3
Verdict: ACCEPTED
input |
---|
10 10 1 1 1 1 2 3 4 4 1 1 8 2 7 8 3 ... |
correct output |
---|
1 1 1 1 1 ... |
user output |
---|
1 1 1 1 1 ... |
Test 4
Verdict: WRONG ANSWER
input |
---|
10 10 1 1 3 1 2 2 5 3 9 7 2 7 6 3 9 ... |
correct output |
---|
2 2 3 1 1 ... |
user output |
---|
1 2 1 1 1 ... |
Test 5
Verdict: WRONG ANSWER
input |
---|
10 10 1 2 3 2 5 3 2 2 4 6 1 1 3 1 9 ... |
correct output |
---|
1 1 1 2 2 ... |
user output |
---|
1 1 1 1 2 ... |
Test 6
Verdict: TIME LIMIT EXCEEDED
input |
---|
200000 200000 1 2 3 4 5 6 7 8 9 10 11 12 13 ... |
correct output |
---|
74862 8750 16237 72298 58111 ... |
user output |
---|
(empty) |
Test 7
Verdict: ACCEPTED
input |
---|
200000 200000 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ... |
correct output |
---|
1 1 1 1 1 ... |
user output |
---|
1 1 1 1 1 ... Truncated |
Test 8
Verdict: WRONG ANSWER
input |
---|
200000 200000 1 2 1 2 3 2 1 6 3 1 10 12 13 4... |
correct output |
---|
1 2 2 2 1 ... |
user output |
---|
1 1 1 1 1 ... Truncated |
Test 9
Verdict: TIME LIMIT EXCEEDED
input |
---|
200000 200000 1 2 3 4 5 6 7 8 9 10 11 12 13 ... |
correct output |
---|
2796 633 633 151 2690 ... |
user output |
---|
(empty) |
Test 10
Verdict: TIME LIMIT EXCEEDED
input |
---|
200000 200000 1 2 3 4 5 6 7 8 9 10 11 12 13 ... |
correct output |
---|
365 73 103 365 216 ... |
user output |
---|
(empty) |
Test 11
Verdict: ACCEPTED
input |
---|
2 4 1 1 1 1 2 2 1 ... |
correct output |
---|
1 1 1 2 |
user output |
---|
1 1 1 2 |
Test 12
Verdict: TIME LIMIT EXCEEDED
input |
---|
200000 200000 1 1 2 3 4 5 6 7 8 9 10 11 12 1... |
correct output |
---|
27468 6353 27468 6353 6353 ... |
user output |
---|
(empty) |