CSES - Aalto Competitive Programming 2024 - wk7 Homework - Results
Submission details
Task:Company Queries II
Sender:laluj
Submission time:2024-10-22 02:15:42 +0300
Language:C++ (C++17)
Status:READY
Result:ACCEPTED
Test results
testverdicttime
#1ACCEPTED0.00 sdetails
#2ACCEPTED0.00 sdetails
#3ACCEPTED0.00 sdetails
#4ACCEPTED0.00 sdetails
#5ACCEPTED0.00 sdetails
#6ACCEPTED0.67 sdetails
#7ACCEPTED0.61 sdetails
#8ACCEPTED0.68 sdetails
#9ACCEPTED0.66 sdetails
#10ACCEPTED0.65 sdetails
#11ACCEPTED0.00 sdetails
#12ACCEPTED0.67 sdetails

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 through
trav_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 node
trav_node_id.push_back(node);
trav_depth.push_back(depth);
}
}
// Structure to represent a query range
struct 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 1
for (int i = 0; i < n; i++)
lookup[i][0] = i;
// Compute values from smaller
// to bigger intervals
for (int j = 1; (1 << j) <= n; j++)
{
// Compute minimum value for
// all intervals with size 2^j
for (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];
else
lookup[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^j
return 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 graph
vector<vi> succ (n);
int e;
for (int i = 1; i < n; i++) {
cin >> e; e--;
succ[e].push_back(i);
}
// Queries
vector<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 graph
vi 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 queries
int 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 traversal
vi 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();
// Results
for (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