This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1e6 + 500;
const int LOG = 21;
int n, k, q, t;
int rod[2][MAXN][LOG], d[2][MAXN], dt[2][MAXN], tim, bio[2][MAXN], rj[2][MAXN];
vector<int> djeca[2][MAXN], v;
vector<pair<int, int> > susjedi[2][MAXN];
void dfs (int x, int br, int g) {
d[g][x] = br;
dt[g][x] = tim++;
for (auto nx: djeca[g][x]) dfs (nx, br + 1, g);
}
bool cmp (int x, int y) {
return dt[1][x] < dt[1][y];
}
int lca (int g, int x, int y) {
if (d[g][x] > d[g][y]) swap (x, y);
for (int i = LOG - 1; i >= 0; i--) {
if (d[g][rod[g][y][i]] >= d[g][x]) y = rod[g][y][i];
}
for (int i = LOG - 1; i >= 0; i--) {
if (rod[g][x][i] != rod[g][y][i]) {
x = rod[g][x][i];
y = rod[g][y][i];
}
}
if (x != y) x = rod[g][x][0];
return x;
}
void dfs2 (int x, int g) {
bio[g][x] = 0;
for (auto it: susjedi[g][x]) {
int nx = it.first;
if (bio[g][nx] != -1) continue;
rj[g][nx] = rj[g][x] + it.second;
dfs2 (nx, g);
}
}
int main () {
memset (bio, -1, sizeof (bio));
cin >> n >> k >> q >> t;
for (int i = 0; i < 2; i++) {
for (int j = 0; j < n; j++) {
int a;
cin >> a;
if (a == -1) rod[i][j][0] = j;
else {
a--;
rod[i][j][0] = a;
djeca[i][a].push_back (j);
}
}
}
for (int i = 0; i < 2; i++) {
for (int j = 1; j < LOG; j++) {
for (int l = 0; l < n; l++) rod[i][l][j] = rod[i][rod[i][l][j - 1]][j - 1];
}
}
for (int i = 0; i < n; i++) {
if (rod[0][i][0] == i) {
tim = 0;
dfs (i, 0, 0);
}
if (rod[1][i][0] == i) {
tim = 0;
dfs (i, 0, 1);
}
}
for (int i = 0; i < n; i++) {
if (dt[0][i] < k) v.push_back (i);
}
sort (v.begin (), v.end (), cmp);
return 0;
for (auto it: v) cout << it + 1 << ' ';
cout << endl;
for (int i = 0; i < k - 1; i++) cout << "? " << v[i] + 1 << ' ' << v[i + 1] + 1 << endl;
cout << '!' << endl;
for (int i = 0; i < k - 1; i++) {
int a, b, c, d;
cin >> a >> b >> c >> d;
int x = v[i], y = v[i + 1];
int lca0 = lca (0, x, y), lca1 = lca (1, x, y);
susjedi[0][lca0].push_back ({x, a});
susjedi[0][x].push_back ({lca0, -a});
susjedi[0][lca0].push_back ({y, b});
susjedi[0][y].push_back ({lca0, -b});
susjedi[1][lca1].push_back ({x, c});
susjedi[1][x].push_back ({lca1, -c});
susjedi[1][lca1].push_back ({y, d});
susjedi[1][y].push_back ({lca1, -d});
}
dfs2 (v[0], 0);
dfs2 (v[0], 1);
for (int i = 0; i < t; i++) {
int a, b;
cin >> a >> b;
a--;b--;
int lca0 = lca (0, a, b), lca1 = lca (1, a, b);
cout << rj[0][a] + rj[0][b] - 2 * rj[0][lca0] << ' ' << rj[1][a] + rj[1][b] - 2 * rj[1][lca1] << endl;
}
return 0;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |