#include<bits/stdc++.h>
#define f first
#define s second
#define int long long
#define pii pair<int,int>
using namespace std;
const int N = 2e5 + 5, mod = 1e9 + 7; // !
int t, tmin[2][N], tmout[2][N], p[2][N][22], timer= 0, k;
pii q[N][2];
int h[2][N], ans[N][2];
vector<int> x,V[2][N];
bool check(int u, int v, int t) {
return (tmin[t][u] <= tmin[t][v] && tmin[t][v] <= tmout[t][u]);
}
int lca(int u,int v, int t) {
if(check(u, v, t)) return u;
if(check(v, u, t))return v;
for(int i = 20; i >= 0; i--) {
if(p[t][u][i] && !check(p[t][u][i], v, t)) u = p[t][u][i];
}
return p[t][u][0];
}
void dfs(int u, int t) {
tmin[t][u] = ++timer;
if(x.size() < k) x.push_back(u);
for(int i = 1; i <= 20; i++) p[t][u][i] = p[t][p[t][u][i - 1]][i - 1];
for(int i = 0; i < V[t][u].size(); i++) p[t][V[t][u][i]][0] = u, dfs(V[t][u][i], t);
tmout[t][u] = timer;
}
bool cmp(int x,int y) {
return (tmin[1][x] < tmin[1][y]);
}
main(){
int n, Q, T;
cin >> n >> k >> Q >> T;
vector<int> r(2);
for(int t = 0; t < 2; ++t) {
for(int i = 1; i <= n; i++) {
int p;
cin >> p;
if(p == -1) r[t] = i;
else V[t][p].push_back(i);
}
}
dfs(r[0], 0);
timer = 0;
dfs(r[1], 1);
sort(x.begin(), x.end(), cmp);
for(int i = 0; i < x.size(); i++) cout << x[i] << " ";
cout << endl;
for(int i = 1; i < x.size(); i++) {
cout << "? " << x[i - 1] << " " << x[i] << endl;
}
cout << "!" << endl;
h[0][x[0]] = h[1][x[0]] = 0;
for(int i = 1; i < x.size(); i++) {
for(int t = 0; t < 2; t++) {
cin >> q[i][t].f >> q[i][t].s;
h[t][lca(x[i - 1], x[i], t)] = h[t][x[i - 1]] - q[i][t].f;
h[t][x[i]] = h[t][x[i - 1]] - q[i][t].f + q[i][t].s;
}
}
for(int i = 1; i <= T; i++) {
int u, v;
cin >> u >> v;
for(int t = 0; t < 2; t++) ans[i][t] = h[t][u] + h[t][v] - 2 * h[t][lca(u, v, t)];
}
for(int i = 1; i <= T; i++) cout << ans[i][0] << " " << ans[i][1] << endl;
}
Compilation message
Main.cpp: In function 'void dfs(long long int, long long int)':
Main.cpp:26:17: warning: comparison of integer expressions of different signedness: 'std::vector<long long int>::size_type' {aka 'long unsigned int'} and 'long long int' [-Wsign-compare]
26 | if(x.size() < k) x.push_back(u);
| ~~~~~~~~~^~~
Main.cpp:28:22: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
28 | for(int i = 0; i < V[t][u].size(); i++) p[t][V[t][u][i]][0] = u, dfs(V[t][u][i], t);
| ~~^~~~~~~~~~~~~~~~
Main.cpp: At global scope:
Main.cpp:34:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
34 | main(){
| ^~~~
Main.cpp: In function 'int main()':
Main.cpp:52:22: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
52 | for(int i = 0; i < x.size(); i++) cout << x[i] << " ";
| ~~^~~~~~~~~~
Main.cpp:54:22: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
54 | for(int i = 1; i < x.size(); i++) {
| ~~^~~~~~~~~~
Main.cpp:59:22: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
59 | for(int i = 1; i < x.size(); i++) {
| ~~^~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
455 ms |
78112 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
435 ms |
78292 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
468 ms |
78296 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
194 ms |
68064 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
65 ms |
52812 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
