| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 805519 |
2023-08-03T17:28:42 Z |
rnl42 |
Prize (CEOI22_prize) |
C++14 |
|
3212 ms |
826092 KB |
#include <bits/stdc++.h>
using namespace std;
using bdata = vector<bool>;
using idata = vector<int>;
using igrid = vector<idata>;
const int MAXK = 21;
struct Tree {
igrid roads;
igrid parents_2k;
idata dist_root;
idata parents;
idata preordre;
idata depth;
int root;
void dfs_preordre (int node, int _depth) {
preordre.push_back(node);
depth[node] = _depth;
for (int next : roads[node])
dfs_preordre(next, _depth + 1);
}
int jump (int node, int k) {
for (int i = 0; i < MAXK; i ++) {
if (((1 << i) & k) == 0) continue ;
node = parents_2k[node][i];
}
return node;
}
int lca (int a, int b) {
if (depth[a] > depth[b]) swap(a, b);
b = jump(b, depth[b] - depth[a]);
if (a == b) return a;
for (int i = MAXK - 1; i >= 0; i --) {
if (parents_2k[a][i] == parents_2k[b][i]) continue ;
a = parents_2k[a][i];
b = parents_2k[b][i];
}
return parents[a];
}
int distance (int a, int b) {
int l = lca(a, b);
return dist_root[a] + dist_root[b] - 2 * dist_root[l];
}
void dfs_compute (idata &distances_to_parent, int distance, int node) {
distance += distances_to_parent[node];
dist_root[node] = distance;
for (int next : roads[node])
dfs_compute(distances_to_parent, distance, next);
}
void compute (idata &distances_to_parent) {
dfs_compute(distances_to_parent, 0, root);
}
Tree () = default;
Tree (int N) {
dist_root.resize(N, -1);
roads .resize(N);
depth .resize(N);
parents .resize(N);
for (int i = 0; i < N; i ++) {
cin >> parents[i];
parents[i] --;
if (parents[i] == -2) {
parents[i] = -1;
root = i;
continue ;
}
roads[parents[i]].push_back(i);
}
dfs_preordre(root, 0);
}
void init_lca (int N) {
parents_2k.resize(N, idata(MAXK, -1));
for (int i = 0; i < N; i ++)
parents_2k[i][0] = parents[i];
for (int k = 0; k + 1 < MAXK; k ++) {
for (int i = 0; i < N; i ++) {
if (parents_2k[i][k] == -1) continue ;
parents_2k[i][k + 1] = parents_2k[parents_2k[i][k]][k];
}
}
}
};
Tree tree1, tree2;
bdata subset;
vector<pair<int, int>> queries;
int last_preordre = -1;
void dfs_query (int node) {
if (subset[node]) {
if (last_preordre != -1) {
queries.push_back({ last_preordre, node });
cout << "? " << last_preordre + 1 << " " << node + 1 << "\n";
}
last_preordre = node;
}
for (int next : tree1.roads[node])
dfs_query(next);
}
int main () {
ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
auto tbegin = chrono::high_resolution_clock::now();
int N, K, Q, T;
cin >> N >> K >> Q >> T;
tree1 = Tree(N);
tree2 = Tree(N);
subset.resize(N);
for (int i = 0; i < K; i ++) {
subset[ tree2.preordre[i] ] = true;
cout << tree2.preordre[i] + 1;
if (i + 1 == K) cout << "\n";
else cout << " ";
}
cout << flush;
dfs_query(tree1.root);
cout << "!\n";
cout << flush;
tree1.init_lca(N);
tree2.init_lca(N);
assert(chrono::duration_cast<chrono::milliseconds>(chrono::high_resolution_clock::now()-tbegin) < 3200ms);
idata distance_to_root1(N, 0);
idata distance_to_root2(N, 0);
for (const auto &query : queries) {
int q1 = query.first;
int q2 = query.second;
int al1, bl1, al2, bl2;
cin >> al1 >> bl1 >> al2 >> bl2;
int lca1 = tree1.lca(q1, q2);
int lca2 = tree2.lca(q1, q2);
distance_to_root1[lca1] = distance_to_root1[q1] - al1;
distance_to_root1[q2 ] = distance_to_root1[q1] + bl1 - al1;
distance_to_root2[lca2] = distance_to_root2[q1] - al2;
distance_to_root2[q2 ] = distance_to_root2[q1] + bl2 - al2;
}
assert(chrono::duration_cast<chrono::milliseconds>(chrono::high_resolution_clock::now()-tbegin) < 3200ms);
tree1.dist_root = distance_to_root1;
tree2.dist_root = distance_to_root2;
for (int i = 0; i < T; i ++) {
int p, q;
cin >> p >> q;
p --; q --;
cout << tree1.distance(p, q) << " " << tree2.distance(p, q) << "\n";
}
cout << flush;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1126 ms |
216188 KB |
Time limit exceeded (wall clock) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1383 ms |
216368 KB |
Time limit exceeded (wall clock) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1044 ms |
215704 KB |
Time limit exceeded (wall clock) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
3212 ms |
770012 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
3070 ms |
826092 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
