Task: | Company Queries II |
Sender: | laluj |
Submission time: | 2024-10-22 02:15:42 +0300 |
Language: | C++ (C++17) |
Status: | READY |
Result: | ACCEPTED |
test | verdict | time | |
---|---|---|---|
#1 | ACCEPTED | 0.00 s | details |
#2 | ACCEPTED | 0.00 s | details |
#3 | ACCEPTED | 0.00 s | details |
#4 | ACCEPTED | 0.00 s | details |
#5 | ACCEPTED | 0.00 s | details |
#6 | ACCEPTED | 0.67 s | details |
#7 | ACCEPTED | 0.61 s | details |
#8 | ACCEPTED | 0.68 s | details |
#9 | ACCEPTED | 0.66 s | details |
#10 | ACCEPTED | 0.65 s | details |
#11 | ACCEPTED | 0.00 s | details |
#12 | ACCEPTED | 0.67 s | details |
Code
#include <bits/stdc++.h>using namespace std;#define debug(x) cerr << #x << ": " << x << endl;#define ll long long#define ull unsigned long long#define vi vector<int>void dfs_traversal(int node, vector<vi>& adj, vi& trav_node_id, vi& trav_depth, int depth) {// Inform the traversal on the node we are going throughtrav_node_id.push_back(node);trav_depth.push_back(depth);// If successors, dfs them ...for (int neighbor : adj[node]) {dfs_traversal(neighbor, adj, trav_node_id, trav_depth, depth + 1);// ... and inform the traversal again for this nodetrav_node_id.push_back(node);trav_depth.push_back(depth);}}// Structure to represent a query rangestruct Query {int A, B;};// Fills lookup array// lookup[][] in bottom up manner.void preprocess(vi& arr, int n, vector<vi>& lookup){// Initialize M for the// intervals with length 1for (int i = 0; i < n; i++)lookup[i][0] = i;// Compute values from smaller// to bigger intervalsfor (int j = 1; (1 << j) <= n; j++){// Compute minimum value for// all intervals with size 2^jfor (int i = 0; (i + (1 << j) - 1) < n; i++){if (arr[lookup[i][j - 1]]< arr[lookup[i + (1 << (j - 1))][j - 1]])lookup[i][j] = lookup[i][j - 1];elselookup[i][j]= lookup[i + (1 << (j - 1))][j - 1];}}}// Returns minimum of arr[L..R]int minqueryidx(vi& arr, int L, int R, vector<vi>& lookup){int j = (int)log2(R - L + 1);int k = (1 << j); // 2^jreturn arr[lookup[L][j]] < arr[lookup[R - k + 1][j]] ?lookup[L][j] : lookup[R - k + 1][j];}int main() {int n,q;cin >> n >> q;stringstream traces;// Successor graphvector<vi> succ (n);int e;for (int i = 1; i < n; i++) {cin >> e; e--;succ[e].push_back(i);}// Queriesvector<Query> queries (q);int a,b;for (int i = 0; i < q; i++) {cin >> a >> b; a--; b--;queries[i].A = a;queries[i].B = b;}// traces << "-------- GRAPH --------" << endl;// for (int i = 0; i < n; i++)// {// traces << i << " -> ";// for (auto& s : succ[i]) traces << s << ' ';// traces << endl;// }// traces << "-----------------------" << endl << endl;// Traversal of the graphvi trav_node_id;vi trav_depth;dfs_traversal(0, succ, trav_node_id, trav_depth, 1);// traces << "-------- TRAVERSAL --------" << endl;// for (auto &&i : trav_node_id) traces << i << ' '; traces << endl;// for (auto &&i : trav_depth) traces << i << ' '; traces << endl;// traces << "---------------------------" << endl << endl;// Preprocessing for min queriesint N = trav_depth.size();vector<vi> lookup (N, vi((int)log2(N) + 1, -1));preprocess(trav_depth, N, lookup);// traces << "-------- LOOKUP TABLE --------" << endl;// for (auto &&v : lookup) {// for (auto &&i : v) traces << i << ' ';// traces << endl;// }// traces << "------------------------------" << endl << endl;// Last position of node_id in traversalvi node_id_trav_idx (n);for (int i = 0; i < N; i++)node_id_trav_idx[trav_node_id[i]] = i;// Queries treatment// traces << "-------- QUERIES --------" << endl;vi res;int r;for (auto &&q : queries){int L = node_id_trav_idx[q.A];int R = node_id_trav_idx[q.B];if (L > R) swap(L,R);// traces << "lowest_common_ancestor(" << q.A << ", " << q.B << ")" <<// " = minqueryidx(" << L << ", " << R << ") = ";r = trav_node_id[minqueryidx(trav_depth, L, R, lookup)];res.push_back(r);// traces << r << endl;}// traces << "-------------------------" << endl;// cout << traces.str();// Resultsfor (auto &&r : res) cout << r + 1 << endl;return 0;}
Test details
Test 1
Verdict: ACCEPTED
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 |
---|
6 8 3 1 8 ... |
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: ACCEPTED
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 |
---|
2 2 3 1 1 ... |
Test 5
Verdict: ACCEPTED
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 2 2 ... |
Test 6
Verdict: ACCEPTED
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 |
---|
74862 8750 16237 72298 58111 ... Truncated |
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: ACCEPTED
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 2 2 2 1 ... Truncated |
Test 9
Verdict: ACCEPTED
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 |
---|
2796 633 633 151 2690 ... Truncated |
Test 10
Verdict: ACCEPTED
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 |
---|
365 73 103 365 216 ... Truncated |
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: ACCEPTED
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 |
---|
27468 6353 27468 6353 6353 ... Truncated |