| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 773015 | doowey | Prize (CEOI22_prize) | C++14 | 0 ms | 0 KiB |
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;
typedef long long ll;
typedef pair<int, int> pii;
#define fi first
#define se second
#define mp make_pair
#define fastIO ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
const int N = (int)1e6 + 10;
const int LOG = 20;
int n, k, q, t;
struct ans{
int d1, d2, d3, d4;
};
vector<pii> questions;
vector<ans> answers;
struct tree{
vector<int> T[N];
vector<int> Q[N];
int dep[N];
int idx;
int root;
void input(){
int p;
for(int i = 1; i <= n; i ++ ){
cin >> p;
if(p == -1){
root = i;
}
else{
T[p].push_back(i);
}
}
}
int up[LOG][N];
int tin[N];
int tout[N];
int tt = 0;
void dfs(int u, int pa){
tt ++ ;
tin[u] = tt;
up[0][u]=pa;
for(int lg = 1; lg < LOG; lg ++ ){
up[lg][u]=up[lg-1][up[lg-1][u]];
}
for(auto x : T[u]){
dfs(x,u);
}
tout[u] = tt;
}
bool is_anc(int u, int v){
return tin[u] <= tin[v] && tout[u] >= tout[v];
}
int lca(int u, int v){
if(is_anc(u, v)) return u;
for(int lg = LOG - 1; lg >= 0 ;lg -- ){
if(!is_anc(up[lg][u], v)) u=up[lg][u];
}
return up[0][u];
}
set<pii> L[N];
void add_edge(int u, int v){
if(u != v){
Q[u].push_back(v);
//Q[v].push_back(mp(u, w));
}
}
int R;
void dfs_virtual(int node){
for(auto x : Q[node]){
L[node].insert();
}
}
vector<int> lis;
vector<int> answ;
void make_questions(vector<int> _li){
lis = _li;
dfs(root, root);
sort(lis.begin(), lis.end(), [&](int x, int y) {return tin[x] < tin[y];});
for(int i = 0 ; i + 1 < lis.size(); i ++ ){
answ.push_back(questions.size());
questions.push_back(mp(lis[i], lis[i+1]));
}
}
void make_virtual(){
vector<int> wh;
for(auto x : lis){
wh.push_back(x);
}
int cur;
for(int i = 0 ; i + 1 < lis.size(); i ++ ){
cur = lca(lis[i], lis[i + 1]);
wh.push_back(cur);
}
sort(wh.begin(), wh.end(), [&](int x, int y) {return tin[x] < tin[y];});
vector<int> stek;
for(auto x : wh){
while(!stek.empty() && is_anc(x, stek.back())) stek.pop_back();
if(!stek.empty()) add_edge(stek.back(), x, 0);
stek.push_back(x);
}
dfs_virtual(big);
}
int get_dist(int i, int j){
int lc = lca(i, j);
return dep[i] + dep[j] - 2 * dep[lc];
}
};
tree A, B;
int main(){
//fastIO;
cin >> n >> k >> q >> t;
vector<int> y;
for(int i = 1; i <= k ; i ++ ){
y.push_back(i);
}
A.input();
B.input();
A.idx = 0;
B.idx = 1;
A.make_questions(y);
B.make_questions(y);
for(auto x : y){
cout << x << " ";
}
cout << "\n";
fflush(stdout);
for(auto x : questions){
cout << "? " << x.fi << " " << x.se << "\n";
}
cout << "!\n";
fflush(stdout);
answers.resize(questions.size());
for(int i = 0 ; i < questions.size(); i ++ ){
cin >> answers[i].d1 >> answers[i].d2 >> answers[i].d3 >> answers[i].d4;
}
A.make_virtual();
B.make_virtual();
int l, r;
vector<pii> qq;
for(int iq = 1; iq <= t; iq ++ ){
cin >> l >> r;
qq.push_back(mp(l, r));
}
for(auto v : qq){
cout << A.get_dist(v.fi,v.se) << " " << B.get_dist(v.fi,v.se) << "\n";
}
fflush(stdout);
return 0;
}