| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 691868 |
2023-01-31T19:14:00 Z |
piOOE |
Prize (CEOI22_prize) |
C++17 |
|
2361 ms |
343084 KB |
#include <bits/stdc++.h>
using namespace std;
#define int int64_t
void massert(bool v) {
if (!v) {
auto start = clock();
int x = 1;
while ((clock() - start) < 5 * CLOCKS_PER_SEC) {
x <<= 1;
x += 1;
}
}
}
struct HLD {
vector<int> par, siz, head, tin, tout, ord, depth;
int dfs1(int i, vector<vector<int>> &g) {
for (int &t: g[i]) {
if (t != par[i]) {
depth[t] = depth[i] + 1;
par[t] = i;
siz[i] += dfs1(t, g);
if (siz[t] > siz[g[i][0]] || g[i][0] == par[i]) swap(t, g[i][0]);
}
}
return siz[i];
}
void dfs2(int i, int &T, const vector<vector<int>> &g) {
tin[i] = T++;
for (int t: g[i]) {
if (t != par[i]) {
head[t] = (T == tin[i] + 1 ? head[i] : t);
dfs2(t, T, g);
}
}
tout[i] = T;
}
HLD() = default;
HLD(vector<vector<int>> g, int r = 0)
: par(g.size(), -1), siz(g.size(), 1), head(g.size(), r), tin(g.size()), ord(g.size()), tout(g.size()),
depth(g.size()) {
dfs1(r, g);
int x = 0;
dfs2(r, x, g);
for (int i = 0; i < g.size(); ++i) ord[tin[i]] = i;
}
vector<pair<int, int>> path(int a, int b) {
vector<pair<int, int>> res;
for (;; b = par[head[b]]) {
if (tin[b] < tin[a]) swap(a, b);
if (tin[head[b]] <= tin[a]) {
res.emplace_back(tin[a], tin[b] + 1);
return res;
}
res.emplace_back(tin[head[b]], tin[b] + 1);
}
}
pair<int, int> subtree(int i) {
return {tin[i], tin[i] + siz[i]};
}
int dist(int a, int b) {
return depth[a] + depth[b] - 2 * depth[lca(a, b)];
}
int lca(int a, int b) {
for (;; b = par[head[b]]) {
if (tin[b] < tin[a]) swap(a, b);
if (tin[head[b]] <= tin[a]) return a;
}
}
bool isp(int a, int b) {
return tin[a] <= tin[b] && tout[a] >= tout[b];
}
} t1, t2;
vector<int> normalize(int n, int root, vector<vector<pair<int, int>>> g) {
vector<int> dist(n, -1);
dist[root] = 0;
vector<bool> used(n);
function<void(int)> dfs = [&](int v) {
used[v] = true;
for (auto [to, w]: g.at(v)) {
if (!used[to]) {
dist[to] = dist[v] + w;
dfs(to);
}
}
};
dfs(root);
return dist;
}
int32_t main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n, k, q, t;
cin >> n >> k >> q >> t;
vector<int> p1(n), p2(n);
int root1 = -1, root2 = -1;
for (int i = 0; i < n; ++i) {
cin >> p1[i];
if (p1[i] == -1) {
root1 = i;
} else {
p1[i] -= 1;
}
}
for (int i = 0; i < n; ++i) {
cin >> p2[i];
if (p2[i] == -1) {
root2 = i;
} else {
p2[i] -= 1;
}
}
massert(max(root1, root2) < n && min(root1, root2) >= 0);
vector<vector<int>> adj(n);
for (int i = 0; i < n; ++i) {
if (p1[i] != -1) {
adj[p1[i]].push_back(i);
}
}
t1 = HLD(adj, root1);
for (int i = 0; i < n; ++i) {
adj[i].clear();
}
for (int i = 0; i < n; ++i) {
if (p2[i] != -1) {
adj[p2[i]].push_back(i);
}
}
t2 = HLD(adj, root2);
vector<pair<int, int>> questions;
vector<int> ord(n);
iota(ord.begin(), ord.end(), 0);
sort(ord.begin(), ord.end(), [&](int i, int j) {
return t1.tin[i] < t1.tin[j];
});
ord.resize(k);
for (int x : ord) {
cout << x + 1 << " \n"[x == ord.back()];
}
sort(ord.begin(), ord.end(), [&](int i, int j) {
return t2.tin[i] < t2.tin[j];
});
for (int i = 1; i < ord.size(); ++i) {
questions.emplace_back(ord[i - 1], ord[i]);
}
assert(questions.size() <= q);
for (auto [x, y]: questions) {
cout << "? " << x + 1 << " " << y + 1 << '\n';
}
cout << "!" << endl;
vector<vector<pair<int, int>>> g1(n), g2(n);
int h1 = ord[0], h2 = ord[0];
vector<int> aa, bb;
auto addEdge = [&](int tt, int x, int y, int w) {
if (x == y) {
return;
}
if (tt == 0) aa.push_back(x), aa.push_back(y);
else bb.push_back(x), bb.push_back(y);
massert(x < n && y < n && x >= 0 && y >= 0);
(tt == 0 ? g1[x] : g2[x]).emplace_back(y, w);
(tt == 0 ? g1[y] : g2[y]).emplace_back(x, -w);
};
for (auto [x, y]: questions) {
int a, b, c, d;
cin >> a >> b >> c >> d;
int c1 = t1.lca(x, y);
int c2 = t2.lca(x, y);
if (t1.isp(c1, h1)) {
h1 = c1;
}
if (t2.isp(c2, h2)) {
h2 = c2;
}
addEdge(0, c1, x, a);
addEdge(0, c1, y, b);
addEdge(1, c2, x, c);
addEdge(1, c2, y, d);
}
auto first = normalize(n, h1, g1);
auto second = normalize(n, h2, g2);
vector<pair<int, int>> queries(t);
for (auto &[a, b]: queries) {
cin >> a >> b;
a -= 1, b -= 1;
}
for (int i: aa) {
assert(first[i] != -1);
}
for (int i: bb) {
assert(second[i] != -1);
}
for (auto [a, b]: queries) {
int dist1 = first[a] - 2 * first[t1.lca(a, b)] + first[b];
int dist2 = second[a] - 2 * second[t2.lca(a, b)] + second[b];
cout << dist1 << " " << dist2 << '\n';
}
return 0;
}
Compilation message
Main.cpp: In constructor 'HLD::HLD(std::vector<std::vector<long int> >, int64_t)':
Main.cpp:19:44: warning: 'HLD::ord' will be initialized after [-Wreorder]
19 | vector<int> par, siz, head, tin, tout, ord, depth;
| ^~~
Main.cpp:19:38: warning: 'std::vector<long int> HLD::tout' [-Wreorder]
19 | vector<int> par, siz, head, tin, tout, ord, depth;
| ^~~~
Main.cpp:46:5: warning: when initialized here [-Wreorder]
46 | HLD(vector<vector<int>> g, int r = 0)
| ^~~
Main.cpp:52:27: warning: comparison of integer expressions of different signedness: 'int64_t' {aka 'long int'} and 'std::vector<std::vector<long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
52 | for (int i = 0; i < g.size(); ++i) ord[tin[i]] = i;
| ~~^~~~~~~~~~
Main.cpp: In function 'int32_t main()':
Main.cpp:177:23: warning: comparison of integer expressions of different signedness: 'int64_t' {aka 'long int'} and 'std::vector<long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
177 | for (int i = 1; i < ord.size(); ++i) {
| ~~^~~~~~~~~~~~
In file included from /usr/include/c++/10/cassert:44,
from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:33,
from Main.cpp:1:
Main.cpp:181:29: warning: comparison of integer expressions of different signedness: 'std::vector<std::pair<long int, long int> >::size_type' {aka 'long unsigned int'} and 'int64_t' {aka 'long int'} [-Wsign-compare]
181 | assert(questions.size() <= q);
| ~~~~~~~~~~~~~~~~~^~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1117 ms |
172336 KB |
Output is correct |
| 2 |
Correct |
1188 ms |
177660 KB |
Output is correct |
| 3 |
Correct |
955 ms |
150904 KB |
Output is correct |
| 4 |
Correct |
966 ms |
148960 KB |
Output is correct |
| 5 |
Correct |
956 ms |
154644 KB |
Output is correct |
| 6 |
Correct |
992 ms |
152924 KB |
Output is correct |
| 7 |
Correct |
1022 ms |
152908 KB |
Output is correct |
| 8 |
Correct |
970 ms |
151352 KB |
Output is correct |
| 9 |
Correct |
904 ms |
150596 KB |
Output is correct |
| 10 |
Correct |
974 ms |
153668 KB |
Output is correct |
| 11 |
Correct |
864 ms |
147360 KB |
Output is correct |
| 12 |
Correct |
940 ms |
152748 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1214 ms |
177276 KB |
Output is correct |
| 2 |
Correct |
1102 ms |
171684 KB |
Output is correct |
| 3 |
Correct |
1058 ms |
159612 KB |
Output is correct |
| 4 |
Correct |
1147 ms |
166112 KB |
Output is correct |
| 5 |
Correct |
1066 ms |
161272 KB |
Output is correct |
| 6 |
Correct |
1096 ms |
155696 KB |
Output is correct |
| 7 |
Correct |
1116 ms |
163176 KB |
Output is correct |
| 8 |
Correct |
1216 ms |
163104 KB |
Output is correct |
| 9 |
Correct |
1138 ms |
169060 KB |
Output is correct |
| 10 |
Correct |
1197 ms |
171060 KB |
Output is correct |
| 11 |
Correct |
1063 ms |
160428 KB |
Output is correct |
| 12 |
Correct |
1173 ms |
170892 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
968 ms |
167736 KB |
Output is correct |
| 2 |
Correct |
986 ms |
167788 KB |
Output is correct |
| 3 |
Correct |
747 ms |
145048 KB |
Output is correct |
| 4 |
Correct |
746 ms |
144936 KB |
Output is correct |
| 5 |
Correct |
748 ms |
144968 KB |
Output is correct |
| 6 |
Correct |
887 ms |
147252 KB |
Output is correct |
| 7 |
Correct |
931 ms |
147100 KB |
Output is correct |
| 8 |
Correct |
856 ms |
147140 KB |
Output is correct |
| 9 |
Correct |
806 ms |
147372 KB |
Output is correct |
| 10 |
Correct |
809 ms |
147344 KB |
Output is correct |
| 11 |
Correct |
809 ms |
147264 KB |
Output is correct |
| 12 |
Correct |
811 ms |
147284 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2096 ms |
335172 KB |
Output is correct |
| 2 |
Correct |
2165 ms |
335072 KB |
Output is correct |
| 3 |
Correct |
1763 ms |
289620 KB |
Output is correct |
| 4 |
Correct |
1721 ms |
289680 KB |
Output is correct |
| 5 |
Correct |
1762 ms |
289664 KB |
Output is correct |
| 6 |
Correct |
1955 ms |
293928 KB |
Output is correct |
| 7 |
Correct |
1939 ms |
301772 KB |
Output is correct |
| 8 |
Correct |
1952 ms |
293860 KB |
Output is correct |
| 9 |
Correct |
1788 ms |
294212 KB |
Output is correct |
| 10 |
Correct |
1848 ms |
294236 KB |
Output is correct |
| 11 |
Correct |
1791 ms |
294140 KB |
Output is correct |
| 12 |
Correct |
1830 ms |
294164 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2361 ms |
343084 KB |
Output is correct |
| 2 |
Correct |
2361 ms |
342872 KB |
Output is correct |
| 3 |
Correct |
1954 ms |
297568 KB |
Output is correct |
| 4 |
Correct |
2059 ms |
308200 KB |
Output is correct |
| 5 |
Correct |
1914 ms |
291660 KB |
Output is correct |
| 6 |
Correct |
2220 ms |
309576 KB |
Output is correct |
| 7 |
Correct |
2162 ms |
301644 KB |
Output is correct |
| 8 |
Correct |
2205 ms |
309644 KB |
Output is correct |
| 9 |
Correct |
2162 ms |
307232 KB |
Output is correct |
| 10 |
Correct |
2057 ms |
304144 KB |
Output is correct |
| 11 |
Correct |
2101 ms |
304112 KB |
Output is correct |
| 12 |
Correct |
2145 ms |
309864 KB |
Output is correct |
