Submission #1228671

#	Time	Username	Problem	Language	Result	Execution time	Memory
1228671		AlperenT_	Prize (CEOI22_prize)	C++17	0 / 100	1405 ms	432364 KiB

Main

#include <bits/stdc++.h> 

#pragma GCC optimize("O3,unroll-loops")
#define pb push_back
#define F first
#define pii pair<ll,ll> 
#define all(a) a.begin(),a.end()
#define S second 
#define sz(a) (int)a.size()
#define rep(i , a , b) for(int i = (a) ; i <= (b) ; i++)
#define per(i , a , b) for(int i = (a) ; i >= (b) ; i--)
#define ld long double
#define ll long long
using namespace std ;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
const int maxn = 1e6 + 10 , lg = 20   , maxk = 100 + 10  , inf = 1e9+ 10 , mod = 1e9 + 9 ;
vector <int> G[2][maxn]; 
int p[2][maxn][lg+1] , d[2][maxn] ;; 
int r1 , r2 , n , q , t  ,k ;

int lca(int t , int v, int u){
    if(d[t][v] > d[t][u])swap(v,u) ;
    rep(i , 0 ,lg){
        if((d[t][u]-d[t][v])>>i&1){
            u = p[t][u][i] ;
        }
    }
    per(i , lg ,0){
        if(p[t][v][i] != p[t][u][i]){
            v = p[t][v][i] ;
            u = p[t][u][i] ;
        }
    }
    if(v==u)return v; 
    return p[t][v][0]; 
}
int st[2][maxn] , cnt =1 ;
void dfs(int t , int v , int par=-1){
    if(par == -1)par= v; 
    p[t][v][0] = par;
    st[t][v] = cnt;cnt++ ;
    rep(i , 1 ,lg)p[t][v][i] = p[t][p[t][v][i-1]][i-1] ;
    for(int u : G[t][v]){
        d[t][u] = d[t][v]+1;
        dfs(t , u , v) ;
    }
}

vector <int> a ; 
void dfs2(int v){
    if(sz(a) < k){
        a.pb(v); 
    }
    for(int u : G[0][v]){
        dfs2(u); 
    }
}
vector <pii> T[2][maxn] ;

void add(int t ,int a , int b , int s){// d[b] - d[a] = s    
    T[t][a].pb({b,s});
    T[t][b].pb({a,-s}) ;
}
int D[2][maxn], mark[2][maxn] ;; 
void dfs3(int t ,int v){
    mark[t][v]  =1 ;
    for(auto [u,w] : T[t][v]){
        if(mark[t][u] == 1)continue ;
        D[t][u] = D[t][v] + w; 
        dfs3(t , u); 
    }
}

signed main(){
    ios_base::sync_with_stdio(0);cin.tie(0) ;
    cin>> n >> k >> q >> t  ;
    rep(i , 1, n){
        int v;
        cin >> v ;
        if(v==-1){
            r1 =i ;
        }else{
            G[0][v].pb(i); 
        }
    }   
    rep(i ,1 , n){
        int v ;cin >> v; 
        if(v==-1){
            r2 =i ;
        }else{
            G[1][v].pb(i) ;
        }
    }
    dfs(0 , r1) ;
    dfs(1 , r2) ;
    dfs2(r1); 
    for(int x : a)cout << x << " ";
    cout << endl ;cout.flush();
    vector <pii> vec ;
    rep(i ,0 , sz(a)-1){
        vec.pb({st[1][a[i]] , a[i]}) ;
    }   
    sort(all(vec)) ;
    rep(i , 0 ,sz(a)-2){
        cout << "? " << vec[i].S << " " << vec[i+1].S <<endl ;cout.flush(); 
    }
    cout << "!" << endl ;cout.flush(); 
    rep(i , 0 ,sz(a)-2){
        int x1,y1 , x2,y2;
        cin >> x1 >> y1 >> x2 >> y2 ;
        int l1 = lca(0 , vec[i].S , vec[i+1].S) , l2 = lca(1 , vec[i].S ,vec[i+1].S) ;
        add(0 , l1 , vec[i].S ,x1) ;
        add(0 , l1 , vec[i+1].S ,y1) ;
        add(1 , l2 , vec[i].S ,x2) ;
        add(1, l2 , vec[i+1].S  ,y2);
    }
    dfs3(0, r1) ;
    int x2 = lca(1 , vec[0].S , vec.back().S) ;
    dfs3(1, x2) ;
    rep(i ,1, t){
        int x , y ;
        cin >> x >> y ;
        int l1 = lca(0 , x,y) , l2 = lca(1 , x , y);
        cout << D[0][x]+D[0][y] - 2*D[0][l1] << " " << D[1][x]+D[1][y]-2*D[1][l2] << endl; 
    }
    cout << endl ;cout.flush();
}
/*
9 3 2 3
2 -1 2 1 1 5 1 4 5
9 4 5 5 7 3 -1 3 7
10 0 0 1 
0 3 13 5
2 1 
1 4 
2 4

*/

• Subtask 1: 0 / 10
• Subtask 2: 0 / 25
• Subtask 3: 0 / 19
• Subtask 4: 0 / 22
• Subtask 5: 0 / 24