| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 788634 |
2023-07-20T12:22:20 Z |
WLZ |
Prize (CEOI22_prize) |
C++17 |
|
3500 ms |
523912 KB |
#include <bits/stdc++.h>
using namespace std;
/** 1-indexed LCA class */
class least_common_ancestor {
private:
int n, max_log, dfs_cnt = 0, root;
vector< vector< pair<int, int> > > g;
vector< vector<int> > up;
vector<int> d, dfs_in, dfs_out;
void dfs(int u, int p) {
dfs_in[u] = dfs_cnt++;
up[u][0] = p;
for (int i = 1; i <= max_log; i++) up[u][i] = up[up[u][i - 1]][i - 1];
for (auto &v : g[u]) {
if (v.first == u) continue;
d[v.first] = d[u] + v.second;
dfs(v.first, u);
}
dfs_out[u] = dfs_cnt;
}
void init() {
n = (int) g.size() - 1;
max_log = ceil(log2(n + 1));
up.assign(n + 1, vector<int>(max_log + 1));
d.assign(n + 1, 0);
dfs_in.resize(n + 1);
dfs_out.resize(n + 1);
dfs(root, root);
}
public:
/** Assumes g is an undirected tree. Can be directed if edges point away from vertex the root */
least_common_ancestor(const vector< vector< pair<int, int> > > &_g, int _root = 1) : root(_root), g(_g) {
init();
}
/** Assigns weight 1 to all edges in an unweighted tree */
least_common_ancestor(const vector< vector<int> > &_g, int _root = 1) : root(_root) {
g.assign((int) _g.size(), vector< pair<int, int> >());
for (int i = 0; i < (int) _g.size(); i++) {
for (auto &x : _g[i]) g[i].emplace_back(x, 1);
}
init();
}
bool is_anc(int u, int v) {
return dfs_in[u] <= dfs_in[v] && dfs_out[v] <= dfs_out[u];
}
int query(int u, int v) {
if (is_anc(u, v)) return u;
if (is_anc(v, u)) return v;
for (int i = max_log; i >= 0; i--) {
if (!is_anc(up[u][i], v)) u = up[u][i];
}
return up[u][0];
}
int depth(int u) {
return d[u];
}
int dist(int u, int v) {
return d[u] + d[v] - 2 * d[query(u, v)];
}
int preorder(int u) {
return dfs_in[u];
}
int postorder(int u) {
return dfs_out[u];
}
};
vector< vector< pair<int, int> > > v_g[2];
void dfs(int u, vector<int> &dist, const vector< vector< pair<int, int> > > &g) {
if (dist[u] == -1) dist[u] = 0;
for (auto &v : g[u]) {
if (dist[v.first] == -1) {
dist[v.first] = dist[u] + v.second;
dfs(v.first, dist, g);
}
}
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
int n, k, q, t;
cin >> n >> k >> q >> t;
int r[2];
vector<int> p[2];
vector< vector<int> > g[2];
for (int idx = 0; idx < 2; idx++) {
p[idx].resize(n + 1);
g[idx].resize(n + 1);
for (int i = 1; i <= n; i++) {
cin >> p[idx][i];
if (p[idx][i] == -1) r[idx] = i;
else g[idx][p[idx][i]].push_back(i);
}
}
least_common_ancestor lca[2] = {least_common_ancestor(g[0], r[0]), least_common_ancestor(g[1], r[1])};
vector<int> x(n);
iota(x.begin(), x.end(), 1);
sort(x.begin(), x.end(), [&](int a, int b) {
return lca[0].preorder(a) < lca[0].preorder(b);
});
x.erase(x.begin() + k, x.end());
sort(x.begin(), x.end(), [&](int a, int b) {
return lca[1].preorder(a) < lca[1].preorder(b);
});
vector<int> pos(n + 1, -1);
for (int i = 0; i < k; i++) {
if (i > 0) cout << ' ';
cout << x[i];
pos[x[i]] = i;
}
cout << endl;
vector<int> virtual_tree = x;
for (int i = 1; i < k; i++) {
cout << "? " << x[i - 1] << ' ' << x[i] << endl;
virtual_tree.push_back(lca[1].query(x[i - 1], x[i]));
}
cout << "!" << endl;
sort(virtual_tree.begin(), virtual_tree.end(), [&](int a, int b) {
return lca[1].preorder(a) < lca[1].preorder(b);
});
virtual_tree.erase(unique(virtual_tree.begin(), virtual_tree.end()), virtual_tree.end());
int v_r = virtual_tree[0];
vector<int> l_0(k), r_0(k), l_1(k), r_1(k);
v_g[0].assign(n + 1, vector< pair<int, int> >());
v_g[1].assign(n + 1, vector< pair<int, int> >());
for (int i = 1; i < k; i++) {
cin >> l_0[i] >> r_0[i] >> l_1[i] >> r_1[i];
int p_0 = lca[0].query(x[i - 1], x[i]), p_1 = lca[1].query(x[i - 1], x[i]);
v_g[0][p_0].emplace_back(x[i - 1], l_0[i]);
v_g[0][x[i - 1]].emplace_back(p_0, -l_0[i]);
v_g[0][p_0].emplace_back(x[i], r_0[i]);
v_g[0][x[i]].emplace_back(p_0, -r_0[i]);
v_g[1][p_1].emplace_back(x[i - 1], l_1[i]);
v_g[1][x[i - 1]].emplace_back(p_1, -l_1[i]);
v_g[1][p_1].emplace_back(x[i], r_1[i]);
v_g[1][x[i]].emplace_back(p_1, -r_1[i]);
}
vector<int> d_0(n + 1, -1), d_1(n + 1, -1);
dfs(r[0], d_0, v_g[0]); dfs(v_r, d_1, v_g[1]);
vector< pair<int, int> > queries(t);
for (int i = 0; i < t; i++) cin >> queries[i].first >> queries[i].second;
for (auto &e : queries) {
int u = e.first, v = e.second;
cout << d_0[u] + d_0[v] - 2 * d_0[lca[0].query(u, v)] << ' ' << d_1[u] + d_1[v] - 2 * d_1[lca[1].query(u, v)] << endl;
}
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2136 ms |
301904 KB |
Output is correct |
| 2 |
Correct |
2015 ms |
304980 KB |
Output is correct |
| 3 |
Correct |
1252 ms |
256232 KB |
Output is correct |
| 4 |
Correct |
1213 ms |
255636 KB |
Output is correct |
| 5 |
Correct |
1291 ms |
258496 KB |
Output is correct |
| 6 |
Correct |
1798 ms |
267776 KB |
Output is correct |
| 7 |
Correct |
1740 ms |
267688 KB |
Output is correct |
| 8 |
Correct |
1781 ms |
267048 KB |
Output is correct |
| 9 |
Correct |
1208 ms |
255884 KB |
Output is correct |
| 10 |
Correct |
1221 ms |
257988 KB |
Output is correct |
| 11 |
Correct |
1202 ms |
254232 KB |
Output is correct |
| 12 |
Correct |
1305 ms |
257244 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2058 ms |
305292 KB |
Output is correct |
| 2 |
Correct |
1831 ms |
300468 KB |
Output is correct |
| 3 |
Correct |
1339 ms |
256068 KB |
Output is correct |
| 4 |
Correct |
1405 ms |
258812 KB |
Output is correct |
| 5 |
Correct |
1303 ms |
257028 KB |
Output is correct |
| 6 |
Correct |
1791 ms |
265216 KB |
Output is correct |
| 7 |
Correct |
1912 ms |
268688 KB |
Output is correct |
| 8 |
Correct |
1854 ms |
269096 KB |
Output is correct |
| 9 |
Correct |
1749 ms |
265920 KB |
Output is correct |
| 10 |
Correct |
1701 ms |
266628 KB |
Output is correct |
| 11 |
Correct |
1713 ms |
262464 KB |
Output is correct |
| 12 |
Correct |
1839 ms |
266388 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1816 ms |
293744 KB |
Output is correct |
| 2 |
Correct |
1881 ms |
293780 KB |
Output is correct |
| 3 |
Correct |
1008 ms |
246908 KB |
Output is correct |
| 4 |
Correct |
935 ms |
246964 KB |
Output is correct |
| 5 |
Correct |
915 ms |
246988 KB |
Output is correct |
| 6 |
Correct |
1279 ms |
257552 KB |
Output is correct |
| 7 |
Correct |
1241 ms |
257600 KB |
Output is correct |
| 8 |
Correct |
1335 ms |
257640 KB |
Output is correct |
| 9 |
Correct |
1103 ms |
254212 KB |
Output is correct |
| 10 |
Correct |
1090 ms |
253952 KB |
Output is correct |
| 11 |
Correct |
1102 ms |
254028 KB |
Output is correct |
| 12 |
Correct |
1095 ms |
254020 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
3545 ms |
523912 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
3527 ms |
523840 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
