#include <bits/stdc++.h>
#define Loop(x,l,r) for (ll x = (l); x < (r); ++x)
#define LoopR(x,l,r) for (ll x = (r)-1; x >= (l); --x)
typedef long long ll;
typedef std::pair<int,int> pii;
using namespace std;
struct tree {
int n;
int rt;
vector<vector<int>> A;
vector<int> pos, ord;
static int constexpr lg = 22;
vector<int> rmq[lg];
void dfs(int v, int &t) {
pos[v] = ord.size();
ord.push_back(v);
for (int u : A[v]) {
dfs(u, t);
ord.push_back(v);
}
}
int mn(int v, int u) const { return pos[v] < pos[u]? v: u; }
void rmqmake() {
rmq[0] = ord;
int n = ord.size();
Loop (i,0,lg-1) {
rmq[i+1].resize(ord.size());
for (int j = 0; j+(2<<i) <= n; ++j)
rmq[i+1][j] = mn(rmq[i][j], rmq[i][j+(1<<i)]);
}
}
int lca(int v, int u) const {
v = pos[v];
u = pos[u];
if (v > u)
swap(v, u);
int len = u-v+1;
int k = __lg(len);
return mn(rmq[k][v], rmq[k][u+1-(1<<k)]);
}
void init0(int sz) {
n = sz;
A.clear();
A.resize(n);
}
void init1() {
pos.resize(n);
ord.clear();
int dard = 0;
dfs(rt, dard);
rmqmake();
}
};
void read_tree(tree &t) {
Loop (i,0,t.n) {
int p;
cin >> p;
--p;
if (p < 0)
t.rt = i;
else
t.A[p].push_back(i);
}
t.init1();
}
vector<int> dis_from_root(const tree &t, const vector<int> &ord, const vector<pii> &res)
{
int p = 0;
while (ord[p] != t.rt)
++p;
vector<int> ans(t.n);
int dis = 0;
Loop (i,p,ord.size()-1) {
dis -= res[i].first;
dis += res[i].second;
ans[ord[i+1]] = dis;
}
dis = 0;
LoopR (i,0,p) {
dis -= res[i].second;
dis += res[i].first;
ans[ord[i]] = dis;
}
return ans;
}
int get_dis(const tree &t, const vector<int> &dis, int v, int u)
{
int l = t.lca(v, u);
return -2*dis[l] + dis[v] + dis[u];
}
int main()
{
ios::sync_with_stdio(false);
tree T1, T2;
int n, k, q, t;
cin >> n >> k >> q >> t;
T1.init0(n);
T2.init0(n);
read_tree(T1);
read_tree(T2);
set<int> myset = {T1.rt, T2.rt};
for (int i = 0; myset.size() < k; ++i)
myset.insert(i);
vector<int> ord(myset.begin(), myset.end());
for (int x : myset)
cout << x+1 << ' ';
cout << '\n';
Loop (i,0,k-1)
cout << "? " << ord[i]+1 << ' ' << ord[i+1]+1 << '\n';
cout << "!\n";
cout.flush();
vector<pii> res1, res2;
Loop (i,0,k-1) {
int a, b, c, d;
cin >> a >> b >> c >> d;
res1.push_back({a, b});
res2.push_back({c, d});
}
vector<int> dis1, dis2;
dis1 = dis_from_root(T1, ord, res1);
dis2 = dis_from_root(T2, ord, res2);
while (t--) {
int v, u;
cin >> v >> u;
--v; --u;
cout << get_dis(T1, dis1, v, u) << ' ';
cout << get_dis(T2, dis2, v, u) << '\n';
}
}
Compilation message
Main.cpp: In function 'std::vector<int> dis_from_root(const tree&, const std::vector<int>&, const std::vector<std::pair<int, int> >&)':
Main.cpp:2:40: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
2 | #define Loop(x,l,r) for (ll x = (l); x < (r); ++x)
| ^
Main.cpp:82:2: note: in expansion of macro 'Loop'
82 | Loop (i,p,ord.size()-1) {
| ^~~~
Main.cpp: In function 'int main()':
Main.cpp:114:31: warning: comparison of integer expressions of different signedness: 'std::set<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
114 | for (int i = 0; myset.size() < k; ++i)
| ~~~~~~~~~~~~~^~~
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Execution timed out |
626 ms |
261700 KB |
Time limit exceeded (wall clock) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Execution timed out |
575 ms |
264312 KB |
Time limit exceeded (wall clock) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Execution timed out |
500 ms |
256964 KB |
Time limit exceeded (wall clock) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Execution timed out |
1284 ms |
513644 KB |
Time limit exceeded (wall clock) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Execution timed out |
1310 ms |
521076 KB |
Time limit exceeded (wall clock) |
| 2 |
Halted |
0 ms |
0 KB |
- |
