| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 842261 |
2023-09-02T16:22:10 Z |
WLZ |
Prize (CEOI22_prize) |
C++17 |
|
3500 ms |
524036 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 |
2015 ms |
302120 KB |
Output is correct |
| 2 |
Correct |
1990 ms |
305344 KB |
Output is correct |
| 3 |
Correct |
1251 ms |
256244 KB |
Output is correct |
| 4 |
Correct |
1195 ms |
256204 KB |
Output is correct |
| 5 |
Correct |
1235 ms |
258900 KB |
Output is correct |
| 6 |
Correct |
1684 ms |
268260 KB |
Output is correct |
| 7 |
Correct |
1674 ms |
268376 KB |
Output is correct |
| 8 |
Correct |
1643 ms |
267492 KB |
Output is correct |
| 9 |
Correct |
1168 ms |
256592 KB |
Output is correct |
| 10 |
Correct |
1225 ms |
258412 KB |
Output is correct |
| 11 |
Correct |
1143 ms |
254880 KB |
Output is correct |
| 12 |
Correct |
1218 ms |
258260 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1757 ms |
306000 KB |
Output is correct |
| 2 |
Correct |
1704 ms |
301284 KB |
Output is correct |
| 3 |
Correct |
1268 ms |
256608 KB |
Output is correct |
| 4 |
Correct |
1360 ms |
259220 KB |
Output is correct |
| 5 |
Correct |
1299 ms |
257672 KB |
Output is correct |
| 6 |
Correct |
1716 ms |
266292 KB |
Output is correct |
| 7 |
Correct |
1851 ms |
269804 KB |
Output is correct |
| 8 |
Correct |
1857 ms |
270064 KB |
Output is correct |
| 9 |
Correct |
1641 ms |
266300 KB |
Output is correct |
| 10 |
Correct |
1655 ms |
267116 KB |
Output is correct |
| 11 |
Correct |
1524 ms |
263328 KB |
Output is correct |
| 12 |
Correct |
1627 ms |
267288 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1580 ms |
294732 KB |
Output is correct |
| 2 |
Correct |
1576 ms |
294688 KB |
Output is correct |
| 3 |
Correct |
887 ms |
247588 KB |
Output is correct |
| 4 |
Correct |
877 ms |
247152 KB |
Output is correct |
| 5 |
Correct |
879 ms |
247596 KB |
Output is correct |
| 6 |
Correct |
1194 ms |
258180 KB |
Output is correct |
| 7 |
Correct |
1183 ms |
258496 KB |
Output is correct |
| 8 |
Correct |
1163 ms |
258108 KB |
Output is correct |
| 9 |
Correct |
1024 ms |
254368 KB |
Output is correct |
| 10 |
Correct |
1051 ms |
254316 KB |
Output is correct |
| 11 |
Correct |
1034 ms |
254392 KB |
Output is correct |
| 12 |
Correct |
1059 ms |
254420 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
3573 ms |
524036 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
3558 ms |
524016 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
