이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> pii;
const int MAXN = 1e6+5;
int N, K, Q, T;
// Tree information
int P[2][MAXN], root[2];
vector<int> child[2][MAXN];
vector<int> ord[2];
int tin[2][MAXN], tout[2][MAXN], depth[2][MAXN];
int subtree_by_ord[MAXN];
pii table[22][3*MAXN]; // used for lca query
void dfs(int curtree, int u, int &cte) {
tin[curtree][u] = ++cte;
ord[curtree].push_back(u);
if (curtree == 0) table[0][cte] = make_pair(depth[curtree][u], u);
for (int v : child[curtree][u]) {
depth[curtree][v] = depth[curtree][u] + 1;
dfs(curtree, v, cte);
++cte;
if (curtree == 0) table[0][cte] = make_pair(depth[curtree][u], u);
}
tout[curtree][u] = ++cte;
}
int lca(int curtree, int u, int v) {
int l = tin[curtree][u], r = tin[curtree][v];
if (l > r) swap(l, r);
int lg2 = 31 - __builtin_clz(r-l+1);
return min(table[lg2][l], table[lg2][r-(1<<lg2)+1]).second;
}
bool sort_by_ord1(int u, int v) {
return tin[1][u] < tin[1][v];
}
// Answer recovery
int result[2][MAXN][2];
// Equation graph for tree 1
int distdata[MAXN];
vector<pii> recov_edge[MAXN];
void recover_dfs(int u) {
for (auto [v, w] : recov_edge[u]) {
if (distdata[v] == -1) {
distdata[v] = distdata[u] + w;
recover_dfs(v);
}
}
}
// Euler tour quicksum for tree 2
int qc[3*MAXN];
// Queries
int query[MAXN][2];
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cin >> N >> K >> Q >> T;
for (int i = 1; i <= N; i++) cin >> P[0][i];
for (int i = 1; i <= N; i++) cin >> P[1][i];
for (int i = 1; i <= N; i++) {
if (P[0][i] != -1) child[0][P[0][i]].push_back(i);
else root[0] = i;
if (P[1][i] != -1) child[1][P[1][i]].push_back(i);
else root[1] = i;
}
// Change to 1-based index
ord[0].push_back(0);
ord[1].push_back(1);
{
for (int i = 0; i <= 3*N; i++) {
table[0][i] = make_pair(INT_MAX, INT_MAX);
}
depth[0][root[0]] = depth[1][root[1]] = 0;
int cte = 0;
dfs(0, root[0], cte);
cte = 0;
dfs(1, root[1], cte);
}
for (int i = 1; i <= K; i++) subtree_by_ord[i] = ord[0][i];
sort(subtree_by_ord+1, subtree_by_ord+K+1, sort_by_ord1);
for (int j = 0; j < 21; j++) {
for (int i = 1; i <= 3*N-(1<<j); i++) {
table[j+1][i] = min(table[j][i], table[j][i+(1<<j)]);
}
}
// Query
for (int i = 1; i <= K; i++) cout << subtree_by_ord[i] << " ";
cout << "\n";
for (int i = 1; i < K; i++) {
cout << "? " << subtree_by_ord[i] << " " << subtree_by_ord[i+1] << "\n";
}
cout << "!" << endl;
for (int i = 1; i < K; i++) {
cin >> result[0][i][0] >> result[0][i][1] >> result[1][i][0] >> result[1][i][1];
}
// Tree 1 answer recovery
for (int i = 1; i < K; i++) {
int u = subtree_by_ord[i], v = subtree_by_ord[i+1], w1 = result[0][i][0], w2 = result[0][i][1];
int uvlca = lca(0, u, v);
recov_edge[uvlca].emplace_back(u, w1);
recov_edge[u].emplace_back(uvlca, -w1);
recov_edge[uvlca].emplace_back(v, w2);
recov_edge[v].emplace_back(uvlca, -w2);
}
fill(distdata+1, distdata+N+1, -1);
distdata[root[0]] = 0;
recover_dfs(root[0]);
// Tree 2 answer recovery
for (int i = 1; i < K; i++) {
int u = subtree_by_ord[i], v = subtree_by_ord[i+1], w1 = result[1][i][0], w2 = result[1][i][1];
qc[tin[1][u]] += w1;
qc[tout[1][u]] -= w1;
qc[tin[1][v]] += w2;
qc[tout[1][v]] -= w2;
}
for (int i = 1; i <= 3*N; i++) qc[i] += qc[i-1];
for (int i = 1; i <= T; i++) cin >> query[i][0] >> query[i][1];
for (int i = 1; i <= T; i++) {
int u = query[i][0], v = query[i][1];
// Tree 1
int uvlca = lca(0, u, v);
//cout << uvlca << ':';
cout << distdata[u] + distdata[v] - 2*distdata[uvlca] << ' ';
// Tree 2;
cout << distdata[u] + distdata[v] - 2*distdata[uvlca] << '\n';
//cout << qc[max(tin[1][u], tin[1][v])] - qc[min(tin[1][u], tin[1][v])] << '\n';
}
cout << endl;
return 0;
}
/*
9 3 2 3
2 -1 2 1 1 5 1 4 5
9 4 5 5 7 3 -1 3 7
*/
/*
10 0 0 1
0 3 13 5
4 2
2 1
1 4
*/
# | 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... |