#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;
struct outp{
int d1, d2, d3, d4;
};
vector<pii> qq;
vector<outp> rr;
vector<int> oo;
struct tree{
int idx;
vector<int> T[N];
int root = -1;
int tt;
int tin[N];
int tout[N];
int up[LOG][N];
void dfs(int u, int pa){
tt ++ ;
tin[u] = tt;
up[0][u] = pa;
for(int ln = 1; ln < LOG; ln ++ ){
up[ln][u]=up[ln-1][up[ln-1][u]];
}
if(oo.size() < k)
oo.push_back(u);
for(auto x : T[u]){
dfs(x, u);
}
tout[u] = tt;
}
void input(){
int p;
for(int i = 1; i <= n; i ++ ){
cin >> p;
if(p == -1) root = i;
else T[p].push_back(i);
}
dfs(root, root);
}
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 ln = LOG - 1; ln >= 0 ; ln -- ){
if(!is_anc(up[ln][u], v)) u = up[ln][u];
}
return up[0][u];
}
vector<int> lis;
vector<int> comp;
void make_queries(vector<int> _s){
lis = _s;
sort(lis.begin(), lis.end(), [&](int x, int y){return tin[x] < tin[y];});
comp = lis;
for(int i = 0 ;i + 1 < lis.size(); i ++ ){
if(idx == 1)
qq.push_back(mp(lis[i], lis[i + 1]));
comp.push_back(lca(lis[i], lis[i + 1]));
}
sort(comp.begin(), comp.end(), [&](int x, int y){return tin[x] < tin[y];});
comp.resize(unique(comp.begin(), comp.end()) - comp.begin());
}
vector<pii> ss[N]; // dep_v = dep_u + x.se
int dep[N];
void add_edge(int u, int v, int w){
ss[u].push_back(mp(v, w));
ss[v].push_back(mp(u, -w));
}
void f(int u){
for(auto x : ss[u]){
if(dep[x.fi] == -1){
dep[x.fi]=dep[u]+x.se;
f(x.fi);
}
}
}
void compute(){
int big;
vector<int> stek;
for(auto x : comp){
while(!stek.empty() && is_anc(x, stek.back())) stek.pop_back();
stek.push_back(x);
}
big = stek[0];
int di, dj;
for(int i = 0 ; i < qq.size(); i ++ ){
int cur = lca(qq[i].fi, qq[i].se);
if(idx == 0){
di = rr[i].d1;
dj = rr[i].d2;
}
else{
di = rr[i].d3;
dj = rr[i].d4;
}
add_edge(cur, qq[i].fi, di);
add_edge(cur, qq[i].se, dj);
}
for(auto x : comp){
dep[x] = -1;
}
dep[big] = 0;
f(big);
}
int get_dist(int i, int j){
int cur = lca(i, j);
return dep[i] + dep[j] - 2 * dep[cur];
}
};
tree ai, bi;
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
int q, t;
cin >> n >> k >> q >> t;
ai.input();
bi.input();
ai.idx = 0;
bi.idx = 1;
ai.make_queries(oo);
bi.make_queries(oo);
for(auto x : oo) cout << x << " ";
cout << "\n";
cout.flush();
fflush(stdout);
for(auto x : qq){
cout << "? " << x.fi << " " << x.se << "\n";
}
cout << "!\n";
cout.flush();
rr.resize(qq.size());
for(int i = 0 ; i < qq.size(); i ++ ){
cin >> rr[i].d1 >> rr[i].d2 >> rr[i].d3 >> rr[i].d4;
}
ai.compute();
bi.compute();
vector<pii> qwe;
int u, v;
for(int it = 1; it <= t; it ++ ){
cin >> u >> v;
qwe.push_back(mp(u, v));
}
for(auto x : qwe){
cout << ai.get_dist(x.fi, x.se) << " " << bi.get_dist(x.fi, x.se) << "\n";
}
cout.flush();
return 0;
}
Compilation message
Main.cpp: In member function 'void tree::dfs(int, int)':
Main.cpp:42:22: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
42 | if(oo.size() < k)
| ~~~~~~~~~~^~~
Main.cpp: In member function 'void tree::make_queries(std::vector<int>)':
Main.cpp:75:30: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
75 | for(int i = 0 ;i + 1 < lis.size(); i ++ ){
| ~~~~~~^~~~~~~~~~~~
Main.cpp: In member function 'void tree::compute()':
Main.cpp:106:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
106 | for(int i = 0 ; i < qq.size(); i ++ ){
| ~~^~~~~~~~~~~
Main.cpp: In function 'int main()':
Main.cpp:154:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
154 | for(int i = 0 ; i < qq.size(); i ++ ){
| ~~^~~~~~~~~~~
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1305 ms |
240784 KB |
Output is correct |
2 |
Correct |
1563 ms |
244868 KB |
Output is correct |
3 |
Correct |
1647 ms |
213176 KB |
Output is correct |
4 |
Correct |
1497 ms |
212196 KB |
Output is correct |
5 |
Correct |
1691 ms |
216128 KB |
Output is correct |
6 |
Correct |
1869 ms |
221216 KB |
Output is correct |
7 |
Correct |
1756 ms |
221200 KB |
Output is correct |
8 |
Correct |
1674 ms |
220164 KB |
Output is correct |
9 |
Correct |
1525 ms |
212924 KB |
Output is correct |
10 |
Correct |
1624 ms |
215416 KB |
Output is correct |
11 |
Correct |
1358 ms |
210584 KB |
Output is correct |
12 |
Correct |
1543 ms |
214716 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1468 ms |
245100 KB |
Output is correct |
2 |
Correct |
1410 ms |
238864 KB |
Output is correct |
3 |
Correct |
1649 ms |
213180 KB |
Output is correct |
4 |
Correct |
1860 ms |
216560 KB |
Output is correct |
5 |
Correct |
1911 ms |
214124 KB |
Output is correct |
6 |
Correct |
2159 ms |
217752 KB |
Output is correct |
7 |
Correct |
2297 ms |
222412 KB |
Output is correct |
8 |
Correct |
2613 ms |
222824 KB |
Output is correct |
9 |
Correct |
2169 ms |
221040 KB |
Output is correct |
10 |
Correct |
2137 ms |
222168 KB |
Output is correct |
11 |
Correct |
2009 ms |
216672 KB |
Output is correct |
12 |
Correct |
2201 ms |
221848 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
941 ms |
227796 KB |
Output is correct |
2 |
Correct |
919 ms |
227860 KB |
Output is correct |
3 |
Correct |
671 ms |
199188 KB |
Output is correct |
4 |
Correct |
731 ms |
199204 KB |
Output is correct |
5 |
Correct |
654 ms |
199240 KB |
Output is correct |
6 |
Correct |
859 ms |
205920 KB |
Output is correct |
7 |
Correct |
894 ms |
205988 KB |
Output is correct |
8 |
Correct |
909 ms |
206024 KB |
Output is correct |
9 |
Correct |
771 ms |
203832 KB |
Output is correct |
10 |
Correct |
779 ms |
203796 KB |
Output is correct |
11 |
Correct |
775 ms |
203852 KB |
Output is correct |
12 |
Correct |
765 ms |
203780 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2376 ms |
363172 KB |
Output is correct |
2 |
Correct |
2162 ms |
363316 KB |
Output is correct |
3 |
Correct |
1628 ms |
306152 KB |
Output is correct |
4 |
Correct |
1589 ms |
305888 KB |
Output is correct |
5 |
Correct |
1691 ms |
305748 KB |
Output is correct |
6 |
Correct |
2144 ms |
319400 KB |
Output is correct |
7 |
Correct |
2354 ms |
319556 KB |
Output is correct |
8 |
Correct |
2392 ms |
319436 KB |
Output is correct |
9 |
Correct |
2219 ms |
315232 KB |
Output is correct |
10 |
Correct |
1996 ms |
315340 KB |
Output is correct |
11 |
Correct |
2173 ms |
315156 KB |
Output is correct |
12 |
Correct |
1932 ms |
315208 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2797 ms |
380256 KB |
Output is correct |
2 |
Correct |
2681 ms |
379432 KB |
Output is correct |
3 |
Correct |
2519 ms |
318160 KB |
Output is correct |
4 |
Correct |
2858 ms |
323648 KB |
Output is correct |
5 |
Correct |
2442 ms |
316824 KB |
Output is correct |
6 |
Execution timed out |
3529 ms |
337264 KB |
Time limit exceeded |
7 |
Halted |
0 ms |
0 KB |
- |