| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 946217 |
2024-03-14T12:19:02 Z |
MinaRagy06 |
Prize (CEOI22_prize) |
C++17 |
|
2795 ms |
460640 KB |
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define SZ(x) (int) x.size()
const int N = 1'000'005;
struct gradingtree {
int n, k, root;
vector<int> P, W;
int t;
int st[N], en[N], anc[N][20];
vector<array<int, 2>> adj[N];
int d[N];
void dfs(int i, int p, int dep) {
anc[i][0] = p;
d[i] = dep;
for (int j = 1; j < 20; j++) {
anc[i][j] = anc[anc[i][j - 1]][j - 1];
}
st[i] = t++;
for (auto [nxt, w] : adj[i]) {
dfs(nxt, i, dep + w);
}
en[i] = t - 1;
}
void init(int _n, int _k, vector<int> &_p, vector<int> &_w) {
n = _n, k = _k, P = _p, W = _w;
for (int i = 1; i <= n; i++) {
if (P[i] == -1) {
root = i;
} else {
adj[P[i]].push_back({i, W[i]});
}
}
dfs(root, root, 0);
// cout << "> ";
// for (int i = 1; i <= n; i++) {
// cout << d[i] << ' ';
// }
// cout << '\n';
}
int lca(int a, int b) {
if (st[a] <= st[b] && en[b] <= en[a]) {
return a;
}
for (int j = 19; j >= 0; j--) {
int c = anc[a][j];
if (!(st[c] <= st[b] && en[b] <= en[c])) {
a = c;
}
}
return anc[a][0];
}
int dist(int a, int b) {
int l = lca(a, b);
// cout << "> " << a << ' ' << b << ": " << d[a] + d[b] - 2 * d[l] << '\n';
return d[a] + d[b] - 2 * d[l];
}
} gt[2];
struct tree {
int n, k, root;
vector<int> P, adj[N], gud;
bool vis[N];
int t;
int st[N], en[N], anc[N][20];
void dfs(int i, int p) {
anc[i][0] = p;
for (int j = 1; j < 20; j++) {
anc[i][j] = anc[anc[i][j - 1]][j - 1];
}
st[i] = t++;
for (auto nxt : adj[i]) {
dfs(nxt, i);
}
en[i] = t - 1;
}
void init(int _n, int _k, vector<int> &_p, vector<int> &_gud) {
n = _n, k = _k, P = _p, gud = _gud;
for (int i = 1; i <= n; i++) {
vis[i] = 0;
if (P[i] == -1) {
root = i;
} else {
adj[P[i]].push_back(i);
}
}
dfs(root, root);
}
int lca(int a, int b) {
if (st[a] <= st[b] && en[b] <= en[a]) {
return a;
}
for (int j = 19; j >= 0; j--) {
int c = anc[a][j];
if (!(st[c] <= st[b] && en[b] <= en[c])) {
a = c;
}
}
return anc[a][0];
}
vector<array<int, 2>> adj2[N];
int d[N];
void dfs2(int i, int c) {
d[i] = c;
vis[i] = 1;
// cout << i << ' ' << d[i] << '\n';
for (auto [nxt, w] : adj2[i]) {
if (vis[nxt]) continue;
dfs2(nxt, c + w);
}
}
void process2() {
int mn = 1e9, node = -1;
for (auto i : gud) {
if (st[i] < mn) {
mn = st[i];
node = i;
}
}
for (int i = 1; i < SZ(gud); i++) {
int x = lca(gud[i - 1], gud[i]);
if (st[x] < mn) {
mn = st[x];
node = x;
}
}
dfs2(node, 0);
}
int dist(int a, int b) {
int l = lca(a, b);
return d[a] + d[b] - 2 * d[l];
}
} t[2];
vector<array<int, 2>> toask;
vector<int> V;
void choose(vector<int> gud) {
#ifndef MINA
for (auto i : gud) {
cout << i << ' ';
}
cout << endl;
#else
V = gud;
#endif
}
void ask(int a, int b) {
toask.push_back({a, b});
}
vector<array<int, 6>> ret;
vector<array<int, 6>> get() {
ret.clear();
#ifndef MINA
for (auto [a, b] : toask) {
cout << "? " << a << ' ' << b << '\n';
}
cout << "!" << endl;
#endif
for (auto [a, b] : toask) {
int al1, bl1, al2, bl2;
#ifndef MINA
cin >> al1 >> bl1 >> al2 >> bl2;
#else
int l1 = gt[0].lca(a, b), l2 = gt[1].lca(a, b);
al1 = gt[0].dist(a, l1);
bl1 = gt[0].dist(b, l1);
al2 = gt[1].dist(a, l2);
bl2 = gt[1].dist(b, l2);
// cout << "? " << a << ' ' << b << "(" << l1 << ", " << l2 << "): " << al1 << ' ' << bl1 << ' ' << al2 << ' ' << bl2 << '\n';
#endif
ret.push_back({a, b, al1, bl1, al2, bl2});
}
return ret;
}
int n, m;
vector<array<int, 6>> v;
void init(int _n, int _m, vector<int> p1, vector<int> p2) {
n = _n, m = _m;
vector<int> gud;
for (int i = 1; i <= m; i++) {
gud.push_back(i);
}
choose(gud);
t[0].init(n, m, p1, gud);
t[1].init(n, m, p2, gud);
for (int i = 1; i < SZ(gud); i++) {
ask(gud[i - 1], gud[i]);
}
v = get();
for (auto [a, b, al1, bl1, al2, bl2] : v) {
int al[2] = {al1, al2};
int bl[2] = {bl1, bl2};
for (int k = 0; k < 2; k++) {
int l = t[k].lca(a, b);
t[k].adj2[l].push_back({a, al[k]});
t[k].adj2[a].push_back({l, -al[k]});
t[k].adj2[l].push_back({b, bl[k]});
t[k].adj2[b].push_back({l, -bl[k]});
}
}
for (int k = 0; k < 2; k++) {
t[k].process2();
// cout << "=========\n";
}
}
array<int, 2> query(int x, int y) {
return {t[0].dist(x, y), t[1].dist(x, y)};
}
vector<int> p1, p2, w1, w2;
vector<array<int, 2>> ans;
void solve() {
int _n, _k, _q, _t;
cin >> _n >> _k >> _q >> _t;
p1.resize(_n + 1);
p2.resize(_n + 1);
for (int i = 1; i <= _n; i++) {
cin >> p1[i];
}
for (int i = 1; i <= _n; i++) {
cin >> p2[i];
}
init(_n, _k, p1, p2);
while (_t--) {
int a, b;
cin >> a >> b;
ans.push_back(query(a, b));
}
for (auto [d1, d2] : ans) {
cout << d1 << ' ' << d2 << '\n';
}
cout << endl;
}
mt19937 rnd(2006);
int rng(int l, int r) {
return rnd() % (r - l + 1) + l;
}
void grader() {
int _n, _k, _q, _t;
cin >> _n >> _k >> _q >> _t;
p1.resize(_n + 1);
p2.resize(_n + 1);
w1.resize(_n + 1);
w2.resize(_n + 1);
for (int i = 1; i <= _n; i++) {
cin >> p1[i];
}
for (int i = 1; i <= _n; i++) {
cin >> p2[i];
}
for (int i = 1; i <= _n; i++) {
cin >> w1[i];
}
for (int i = 1; i <= _n; i++) {
cin >> w2[i];
}
gt[0].init(_n, _k, p1, w1);
gt[1].init(_n, _k, p2, w2);
init(_n, _k, p1, p2);
while (_t--) {
int a = rng(0, V.size() - 1), b = rng(0, V.size() - 1);
a = V[a], b = V[b];
if (query(a, b) != (array<int, 2>) {gt[0].dist(a, b), gt[1].dist(a, b)}) {
cout << "WA\n";
exit(0);
}
}
cout << "OK\n";
}
int main() {
ios_base::sync_with_stdio(0), cin.tie(0);
#ifdef MINA
grader();
#else
solve();
#endif
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1378 ms |
320796 KB |
Output is correct |
| 2 |
Correct |
1402 ms |
325740 KB |
Output is correct |
| 3 |
Runtime error |
687 ms |
294588 KB |
Execution killed with signal 13 |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1448 ms |
325452 KB |
Output is correct |
| 2 |
Correct |
1255 ms |
318064 KB |
Output is correct |
| 3 |
Runtime error |
637 ms |
295268 KB |
Execution killed with signal 13 |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
856 ms |
309724 KB |
Output is correct |
| 2 |
Correct |
881 ms |
309528 KB |
Output is correct |
| 3 |
Runtime error |
517 ms |
282856 KB |
Execution killed with signal 13 |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2122 ms |
444724 KB |
Output is correct |
| 2 |
Correct |
2025 ms |
444340 KB |
Output is correct |
| 3 |
Runtime error |
1211 ms |
387368 KB |
Execution killed with signal 13 |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2795 ms |
460640 KB |
Output is correct |
| 2 |
Correct |
2750 ms |
459056 KB |
Output is correct |
| 3 |
Runtime error |
1297 ms |
397140 KB |
Execution killed with signal 13 |
| 4 |
Halted |
0 ms |
0 KB |
- |
