#include <bits/stdc++.h>
#define debug(x) cerr << #x << " " << x << "\n"
#define debugs(x) cerr << #x << " " << x << " "
#pragma GCC optimize ("Ofast")
#pragma GCC target ("avx2")
using namespace std;
typedef long long ll;
typedef pair <int, int> pii;
const ll NMAX = 1000001;
const int INF = 1e9;
const ll nrbits = 20;
const ll MOD = 998244353;
const int VMAX = 10;
int n;
class Tree{
public:
vector <int> v[NMAX];
int dp[nrbits + 1][NMAX];
vector <int> preorder;
pii timp[NMAX];
int stamp, root;
void init(){
preorder.clear();
stamp = root = 0;
for(int i = 0; i <= n; i++){
v[i].clear();
timp[i].first = timp[i].second = 0;
}
for(int j = 0; j <= nrbits; j++){
for(int i = 0; i <= n; i++)
dp[j][i] = 0;
}
}
bool isParent(int a, int b){
return timp[a].first <= timp[b].first && timp[b].second <= timp[a].second;
}
int LCA(int a, int b){
int r = a, pas = nrbits;
while(pas >= 0){
int nxt = dp[pas][r];
if(nxt != 0 && !isParent(nxt, b)){
r = nxt;
}
pas--;
}
if(!isParent(r, b))
r = dp[0][r];
return r;
}
void setFather(int a, int b){
if(a == -1){
root = b;
return;
}
v[b].push_back(a);
v[a].push_back(b);
}
void DFS(int node, int p){
preorder.push_back(node);
timp[node].first = ++stamp;
dp[0][node] = p;
for(auto x : v[node]){
if(x == p) continue;
DFS(x, node);
}
timp[node].second = stamp;
}
void prec(){
for(int j = 1; j <= nrbits; j++){
for(int i = 1; i <= n; i++){
dp[j][i] = dp[j - 1][dp[j - 1][i]];
}
}
}
}arb1, arb2;
class DSU{ /// Momentan DSU doar cu numele
public:
vector <pii> v[NMAX];
int dist[NMAX];
void init(){
for(int i = 1; i <= n; i++){
v[i].clear();
dist[i] = 2e9;
}
}
void setDistance(int a, int b, int c){
v[a].push_back({b, c});
v[b].push_back({a, -c});
}
void DFS(int node){
for(auto x : v[node]){
if(dist[x.first] == 2e9){
dist[x.first] = x.second + dist[node];
DFS(x.first);
}
}
}
void baga(int x){
dist[x] = 0;
DFS(x);
}
}dsu1, dsu2;
pii sol[NMAX];
bool cmp(int a, int b){
return arb2.timp[a].first < arb2.timp[b].first;
}
signed main() {
#ifdef HOME
// ifstream cin(".in");
// ofstream cout(".out");
#endif // HOME
int k, q, t, rt1 = 0, rt2 = 0;
cin >> n >> k >> q >> t;
arb1.init();
arb2.init();
dsu1.init();
dsu2.init();
for(int i = 1; i <= n; i++){
int p;
cin >> p;
arb1.setFather(p, i);
}
for(int i = 1; i <= n; i++){
int p;
cin >> p;
arb2.setFather(p, i);
}
arb1.DFS(arb1.root, 0);
arb2.DFS(arb2.root, 0);
arb1.prec();
arb2.prec();
vector <int> chosen;
for(int i = 0; i < k; i++){
chosen.push_back(arb1.preorder[i]);
}
for(auto x : chosen){
cout << x << " ";
}
cout << "\n";
sort(chosen.begin(), chosen.end(), cmp);
for(int i = 0; i < chosen.size() - 1; i++){
cout << "? " << chosen[i] << " " << chosen[i + 1] << "\n";
}
cout << "!" << endl;
int minim = 2e9;
int cine = 0;
for(int i = 0; i < chosen.size() - 1; i++){
int a, b, c, d;
cin >> a >> b >> c >> d;
int lca1 = arb1.LCA(chosen[i], chosen[i + 1]);
int lca2 = arb2.LCA(chosen[i], chosen[i + 1]);
if(arb2.timp[lca2].first < minim){
minim = arb2.timp[lca2].first;
cine = lca2;
}
dsu1.setDistance(lca1, chosen[i], a);
dsu1.setDistance(lca1, chosen[i + 1], b);
dsu2.setDistance(lca2, chosen[i], c);
dsu2.setDistance(lca2, chosen[i + 1], d);
}
dsu1.baga(arb1.root);
dsu2.baga(cine);
for(int i = 0; i < t; i++){
int a, b;
cin >> a >> b;
int lca1 = arb1.LCA(a, b);
int lca2 = arb2.LCA(a, b);
sol[i] = {dsu1.dist[a] - 2 * dsu1.dist[lca1] + dsu1.dist[b], dsu2.dist[a] - 2 * dsu2.dist[lca2] + dsu2.dist[b]};
}
for(int i = 0; i < t; i++){
cout << sol[i].first << " " << sol[i].second << "\n";
}
cout << endl;
return 0;
}
Compilation message
Main.cpp: In function 'int main()':
Main.cpp:150:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
150 | for(int i = 0; i < chosen.size() - 1; i++){
| ~~^~~~~~~~~~~~~~~~~~~
Main.cpp:156:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
156 | for(int i = 0; i < chosen.size() - 1; i++){
| ~~^~~~~~~~~~~~~~~~~~~
Main.cpp:120:18: warning: unused variable 'rt1' [-Wunused-variable]
120 | int k, q, t, rt1 = 0, rt2 = 0;
| ^~~
Main.cpp:120:27: warning: unused variable 'rt2' [-Wunused-variable]
120 | int k, q, t, rt1 = 0, rt2 = 0;
| ^~~
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1778 ms |
260152 KB |
Output is correct |
2 |
Correct |
2012 ms |
262648 KB |
Output is correct |
3 |
Correct |
1044 ms |
248460 KB |
Output is correct |
4 |
Correct |
1048 ms |
246048 KB |
Output is correct |
5 |
Correct |
1083 ms |
250308 KB |
Output is correct |
6 |
Correct |
1701 ms |
249096 KB |
Output is correct |
7 |
Correct |
1691 ms |
251028 KB |
Output is correct |
8 |
Correct |
1560 ms |
248768 KB |
Output is correct |
9 |
Correct |
1002 ms |
247892 KB |
Output is correct |
10 |
Correct |
1126 ms |
252176 KB |
Output is correct |
11 |
Correct |
981 ms |
246796 KB |
Output is correct |
12 |
Correct |
1057 ms |
251368 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2224 ms |
265568 KB |
Output is correct |
2 |
Correct |
1760 ms |
261020 KB |
Output is correct |
3 |
Correct |
1018 ms |
249796 KB |
Output is correct |
4 |
Correct |
1086 ms |
250784 KB |
Output is correct |
5 |
Correct |
1124 ms |
251308 KB |
Output is correct |
6 |
Correct |
1655 ms |
247048 KB |
Output is correct |
7 |
Correct |
1867 ms |
250284 KB |
Output is correct |
8 |
Correct |
1874 ms |
250748 KB |
Output is correct |
9 |
Correct |
1576 ms |
252732 KB |
Output is correct |
10 |
Correct |
1635 ms |
251856 KB |
Output is correct |
11 |
Correct |
1470 ms |
248432 KB |
Output is correct |
12 |
Correct |
1600 ms |
251740 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
893 ms |
255388 KB |
Output is correct |
2 |
Correct |
897 ms |
255064 KB |
Output is correct |
3 |
Correct |
752 ms |
240524 KB |
Output is correct |
4 |
Correct |
681 ms |
239144 KB |
Output is correct |
5 |
Correct |
728 ms |
239052 KB |
Output is correct |
6 |
Correct |
811 ms |
240596 KB |
Output is correct |
7 |
Correct |
792 ms |
240600 KB |
Output is correct |
8 |
Correct |
813 ms |
241104 KB |
Output is correct |
9 |
Correct |
753 ms |
243212 KB |
Output is correct |
10 |
Correct |
759 ms |
241292 KB |
Output is correct |
11 |
Correct |
750 ms |
242648 KB |
Output is correct |
12 |
Correct |
760 ms |
242808 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2251 ms |
386220 KB |
Output is correct |
2 |
Correct |
2204 ms |
386744 KB |
Output is correct |
3 |
Correct |
1721 ms |
357304 KB |
Output is correct |
4 |
Correct |
1654 ms |
357088 KB |
Output is correct |
5 |
Correct |
1672 ms |
356960 KB |
Output is correct |
6 |
Correct |
2082 ms |
360840 KB |
Output is correct |
7 |
Correct |
2079 ms |
362592 KB |
Output is correct |
8 |
Correct |
2041 ms |
361012 KB |
Output is correct |
9 |
Correct |
1974 ms |
362928 KB |
Output is correct |
10 |
Correct |
2005 ms |
363244 KB |
Output is correct |
11 |
Correct |
1963 ms |
361364 KB |
Output is correct |
12 |
Correct |
1909 ms |
362772 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
3399 ms |
394868 KB |
Output is correct |
2 |
Correct |
3311 ms |
395836 KB |
Output is correct |
3 |
Correct |
1922 ms |
362968 KB |
Output is correct |
4 |
Correct |
2029 ms |
366544 KB |
Output is correct |
5 |
Correct |
1862 ms |
362296 KB |
Output is correct |
6 |
Correct |
3168 ms |
370936 KB |
Output is correct |
7 |
Correct |
2856 ms |
366564 KB |
Output is correct |
8 |
Correct |
2966 ms |
368956 KB |
Output is correct |
9 |
Correct |
2633 ms |
369580 KB |
Output is correct |
10 |
Correct |
2466 ms |
368372 KB |
Output is correct |
11 |
Correct |
2562 ms |
368752 KB |
Output is correct |
12 |
Correct |
2558 ms |
371704 KB |
Output is correct |