| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 915851 |
2024-01-24T19:13:24 Z |
Alcabel |
Prize (CEOI22_prize) |
C++17 |
|
3500 ms |
396824 KB |
#pragma GCC optimize("O3", "Ofast")
#include <bits/stdc++.h>
using namespace std;
struct DSU {
int n;
vector<int> par;
DSU() {}
DSU(int _n) {
n = _n;
par.resize(n);
clear();
}
void clear() {
for (int i = 0; i < n; ++i) {
par[i] = i;
}
}
int getParent(int v) {
if (par[v] != v) {
par[v] = getParent(par[v]);
}
return par[v];
}
void uniteSets(int v, int u) {
v = getParent(v), u = getParent(u);
if (v == u) {
return;
}
par[u] = v;
}
~DSU() {}
};
const int maxn = 1e6;
vector<int> g1[maxn], g2[maxn];
int tin1[maxn], tout1[maxn], tin2[maxn], tout2[maxn], tt;
void dfs1(int v) {
tin1[v] = tt++;
for (const int& u : g1[v]) {
dfs1(u);
}
tout1[v] = tt++;
}
vector<int> vset;
void dfs2(int v, int k) {
tin2[v] = tt++;
// cerr << "v: " << v + 1 << '\n';
if ((int)vset.size() < k) {
// cerr << "hui\n";
vset.emplace_back(v);
}
for (const int& u : g2[v]) {
dfs2(u, k);
}
tout2[v] = tt++;
}
vector<pair<int, int>> queries[maxn];
const int maxq = 1e5;
int ans[maxq];
DSU dsu;
void dfsAns1(int v) {
while (!queries[v].empty()) {
ans[queries[v].back().second] = dsu.getParent(queries[v].back().first);
queries[v].pop_back();
}
for (const int& u : g1[v]) {
dfsAns1(u);
dsu.uniteSets(v, u);
}
}
void dfsAns2(int v) {
while (!queries[v].empty()) {
ans[queries[v].back().second] = dsu.getParent(queries[v].back().first);
queries[v].pop_back();
}
for (const int& u : g2[v]) {
dfsAns2(u);
dsu.uniteSets(v, u);
}
}
vector<pair<int, int>> w1[maxn], w2[maxn];
char vis[maxn];
int dist1[maxn], dist2[maxn];
void dfsCalc1(int v) {
// cerr << "v: " << v + 1 << ", dist1: " << dist1[v] << '\n';
vis[v] = tt;
for (const auto [u, delta] : w1[v]) {
if (vis[u] < tt) {
dist1[u] = dist1[v] + delta;
dfsCalc1(u);
}
}
}
void dfsCalc2(int v) {
// cerr << "v: " << v + 1 << ", dist2: " << dist2[v] << '\n';
vis[v] = tt;
for (const auto& [u, delta] : w2[v]) {
if (vis[u] < tt) {
dist2[u] = dist2[v] + delta;
dfsCalc2(u);
}
}
}
void solve() {
int n, k, q, t;
cin >> n >> k >> q >> t;
int root1 = -1, root2 = -1;
for (int i = 0; i < n; ++i) {
int p;
cin >> p;
--p;
if (p != -2) {
g1[p].emplace_back(i);
} else {
root1 = i;
}
}
for (int i = 0; i < n; ++i) {
int p;
cin >> p;
--p;
if (p != -2) {
g2[p].emplace_back(i);
} else {
root2 = i;
}
}
tt = 0;
dfs1(root1);
tt = 0;
dfs2(root2, k);
for (const int& v : vset) {
cout << v + 1 << ' ';
}
cout << endl;
sort(vset.begin(), vset.end(), [&](const int& A, const int& B) {
return tin1[A] < tin1[B];
});
dsu = DSU(n);
for (int i = 0; i < k - 1; ++i) {
int v = vset[i], u = vset[i + 1];
// cerr << "v: " << v + 1 << ", u: " << u + 1 << '\n';
queries[u].emplace_back(v, i);
}
dfsAns1(root1);
int comproot1 = -1;
vector<int> lca1(k - 1);
for (int i = 0; i < k - 1; ++i) {
lca1[i] = ans[i];
// cerr << "i: " << i << ", lca1: " << lca1[i] + 1 << '\n';
if (comproot1 == -1 || tin1[comproot1] > tin1[ans[i]]) {
comproot1 = ans[i];
}
int v = vset[i], u = vset[i + 1];
if (tin2[v] > tin2[u]) {
swap(v, u);
}
queries[u].emplace_back(v, i);
}
dsu.clear();
dfsAns2(root2);
int comproot2 = -1;
vector<int> lca2(k - 1);
for (int i = 0; i < k - 1; ++i) {
lca2[i] = ans[i];
// cerr << "i: " << i << ", lca2: " << lca2[i] + 1 << '\n';
if (comproot2 == -1 || tin2[comproot2] > tin2[ans[i]]) {
comproot2 = ans[i];
}
}
for (int i = 0; i < k - 1; ++i) {
cout << "? " << vset[i] + 1 << ' ' << vset[i + 1] + 1 << '\n';
}
cout << "!" << endl;
for (int i = 0; i < k - 1; ++i) {
int v = vset[i], u = vset[i + 1];
int d1v, d1u, d2v, d2u;
cin >> d1v >> d1u >> d2v >> d2u;
w1[lca1[i]].emplace_back(v, d1v);
w1[lca1[i]].emplace_back(u, d1u);
w1[v].emplace_back(lca1[i], -d1v);
w1[u].emplace_back(lca1[i], -d1u);
w2[lca2[i]].emplace_back(v, d2v);
w2[lca2[i]].emplace_back(u, d2u);
w2[v].emplace_back(lca2[i], -d2v);
w2[u].emplace_back(lca2[i], -d2u);
}
dist1[comproot1] = 0;
tt = 1;
dfsCalc1(comproot1);
dist2[comproot2] = 0;
++tt;
dfsCalc2(comproot2);
vector<pair<int, int>> toAsk(t);
for (int i = 0; i < t; ++i) {
int v, u;
cin >> v >> u;
--v, --u;
toAsk[i] = {v, u};
if (tin1[v] > tin1[u]) {
swap(v, u);
}
queries[u].emplace_back(v, i);
}
vector<int> part1(t), part2(t);
dsu.clear();
dfsAns1(root1);
for (int i = 0; i < t; ++i) {
// cerr << "i: " << i << ", lca1: " << ans[i] + 1 << '\n';
auto [v, u] = toAsk[i];
part1[i] = -2ll * dist1[ans[i]] + dist1[v] + dist1[u];
if (tin2[v] > tin2[u]) {
swap(v, u);
}
queries[u].emplace_back(v, i);
}
dsu.clear();
dfsAns2(root2);
for (int i = 0; i < t; ++i) {
// cerr << "i: " << i << ", lca2: " << ans[i] + 1 << '\n';
auto [v, u] = toAsk[i];
part2[i] = -2ll * dist2[ans[i]] + dist2[v] + dist2[u];
cout << part1[i] << ' ' << part2[i] << '\n';
}
cout << endl;
}
int main() {
/*ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);*/
#ifdef LOCALa
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
int T = 1;
cin >> T;
while (T--) {
solve();
cerr << "-----------\n";
cout << "-----------\n";
}
#else
int T = 1;
// cin >> T;
while (T--) {
solve();
}
#endif
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2008 ms |
273912 KB |
Output is correct |
| 2 |
Correct |
2073 ms |
277480 KB |
Output is correct |
| 3 |
Correct |
1104 ms |
173916 KB |
Output is correct |
| 4 |
Correct |
1152 ms |
173116 KB |
Output is correct |
| 5 |
Correct |
1192 ms |
176428 KB |
Output is correct |
| 6 |
Correct |
1500 ms |
194524 KB |
Output is correct |
| 7 |
Correct |
1538 ms |
194472 KB |
Output is correct |
| 8 |
Correct |
1447 ms |
193436 KB |
Output is correct |
| 9 |
Correct |
1136 ms |
173548 KB |
Output is correct |
| 10 |
Correct |
1182 ms |
175240 KB |
Output is correct |
| 11 |
Correct |
1083 ms |
171708 KB |
Output is correct |
| 12 |
Correct |
1178 ms |
174892 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2164 ms |
277552 KB |
Output is correct |
| 2 |
Correct |
1982 ms |
272352 KB |
Output is correct |
| 3 |
Correct |
1175 ms |
173748 KB |
Output is correct |
| 4 |
Correct |
1239 ms |
177324 KB |
Output is correct |
| 5 |
Correct |
1153 ms |
174900 KB |
Output is correct |
| 6 |
Correct |
1453 ms |
192336 KB |
Output is correct |
| 7 |
Correct |
1552 ms |
196428 KB |
Output is correct |
| 8 |
Correct |
1524 ms |
196748 KB |
Output is correct |
| 9 |
Correct |
1400 ms |
195368 KB |
Output is correct |
| 10 |
Correct |
1382 ms |
196480 KB |
Output is correct |
| 11 |
Correct |
1337 ms |
191480 KB |
Output is correct |
| 12 |
Correct |
1375 ms |
195908 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1818 ms |
264052 KB |
Output is correct |
| 2 |
Correct |
1973 ms |
264620 KB |
Output is correct |
| 3 |
Correct |
1047 ms |
162688 KB |
Output is correct |
| 4 |
Correct |
898 ms |
162592 KB |
Output is correct |
| 5 |
Correct |
977 ms |
162124 KB |
Output is correct |
| 6 |
Correct |
1255 ms |
182984 KB |
Output is correct |
| 7 |
Correct |
1192 ms |
182844 KB |
Output is correct |
| 8 |
Correct |
1185 ms |
182516 KB |
Output is correct |
| 9 |
Correct |
1044 ms |
180108 KB |
Output is correct |
| 10 |
Correct |
1070 ms |
180304 KB |
Output is correct |
| 11 |
Correct |
1016 ms |
180204 KB |
Output is correct |
| 12 |
Correct |
1135 ms |
180184 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
3558 ms |
384828 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
3571 ms |
396824 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
