Submission #1236847

#	Time	Username	Problem	Language	Result	Execution time	Memory
1236847		caacrugon	Prize (CEOI22_prize)	C++20	10 / 100	1624 ms	637056 KiB

Main

#include <bits/stdc++.h>

using namespace std;

#define ll long long
#define mkp make_pair

bool dfsMinimunTree(ll u, ll parent, set<ll>&s, vector<vector<ll>>&tree2, vector<vector<pair<ll,ll>>>&newtree2){
    bool co=(s.count(u)>0);
    for(ll i=0;i<tree2[u].size();i++){
        if(tree2[u][i]==parent)continue;
        if(dfsMinimunTree(tree2[u][i],u,s,tree2,newtree2)){
            co=true;
            newtree2[u].push_back(mkp(tree2[u][i],0));
            newtree2[tree2[u][i]].push_back(mkp(u,0));
        }
    }
    return co;
}

void dfsLCA(ll u, ll p, vector<vector<pair<ll,ll>>>&T, vector<vector<ll>>&up, vector<ll>&depth, vector<ll>&dist){
    up[0][u]=p;
    for(int i=0;i<T[u].size();i++){
        if(T[u][i].first==p)continue;
        depth[T[u][i].first]=depth[u]+1;
        dist[T[u][i].first]=dist[u]+T[u][i].second;
        dfsLCA(T[u][i].first,u,T,up,depth,dist);
    }
}

void BLCA(vector<vector<pair<ll,ll>>>&T, vector<vector<ll>>&up, vector<ll>&depth, vector<ll>&dist, ll root, ll N, ll K){
    ll LOG=1;
    while((1<<LOG)<=K)LOG++;
    up.assign(LOG,vector<ll>(N+1,0));
    depth.assign(N+1,0);
    dist.assign(N+1,0);
    dfsLCA(root,0,T,up,depth,dist);
    for(ll i=1;i<LOG;i++){
        for(ll j=1;j<=N;j++){
            up[i][j]=up[i-1][j]?up[i-1][up[i-1][j]]:0;
        }
    }
}

ll GLCA(vector<vector<ll>>&up, vector<ll>&depth, ll a, ll b){
    if(depth[a]<depth[b]) swap(a,b);
    ll diff=depth[a]-depth[b];
    ll LOG=up.size();
    for(ll i=0;i<LOG;i++)if(diff & (1<<i))a=up[i][a];
    if (a==b) return a;
    for(ll i=LOG-1;i>=0;i--){
        if(up[i][a] && up[i][a]!=up[i][b]){
            a=up[i][a];
            b=up[i][b];
        }
    }
    return up[0][a];
}

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    ll N,K,Q,T;
    cin>>N>>K>>Q>>T;
    vector<vector<ll>> tree1(N+1,vector<ll>(0)),tree2(N+1,vector<ll>(0));
    ll r1=0,r2=0;
    for(ll i=1;i<N+1;i++){
        ll a;
        cin>>a;
        if(a==-1){
            r1=i;
            continue;
        }
        tree1[a].push_back(i);
        tree1[i].push_back(a);
    }
    for(ll i=1;i<N+1;i++){
        ll a;
        cin>>a;
        if(a==-1){
            r2=i;
            continue;
        }
        tree2[a].push_back(i);
        tree2[i].push_back(a);
    }
    queue<ll> q;
    q.push(r1);
    vector<bool> visited(N+1,false);
    ll co=K;
    co--;
    cout<<r1<<" ";
    vector<vector<pair<ll,ll>>> newtree1(N+1,vector<pair<ll,ll>>(0)),newtree2(N+1,vector<pair<ll,ll>>(0));
    set<ll> s;
    s.insert(r1);
    while(q.size() && co>0){
        ll nodo=q.front();
        q.pop();
        visited[nodo]=true;
        for(ll i=0;i<tree1[nodo].size() && co>0;i++){
            if(visited[tree1[nodo][i]])continue;
            newtree1[nodo].push_back(mkp(tree1[nodo][i],0));
            co--;
            q.push(tree1[nodo][i]);
            s.insert(tree1[nodo][i]);
            cout<<tree1[nodo][i]<<" ";
        }
    }
    dfsMinimunTree(r2,0,s,tree2,newtree2);
    vector<pair<ll,ll>> edges;
    for(ll i=1;i<=N;i++){
        for(ll j=0;j<newtree1[i].size();j++){
            if(i!=newtree1[i][j].first) edges.push_back(mkp(i,newtree1[i][j].first));
        }
    }
    cout<<"\n";
    for(ll i=0;i<edges.size();i++){
        cout<<"? "<<edges[i].first<<" "<<edges[i].second<<'\n';
    }
    cout<<"!\n";
    cout<<flush;
    fflush(stdout);
    for(ll i=0;i<edges.size();i++){
        ll d1u,d1v,d2u,d2v;
        cin>>d1u>>d1v>>d2u>>d2v;
        ll peso1=d1u+d1v;
        ll peso2=d2u+d2v;
        for(ll j=0;j<newtree1[edges[i].first].size();j++){
            if(newtree1[edges[i].first][j].first==edges[i].second){ 
                newtree1[edges[i].first][j].second=peso1; 
                break; 
            }
        }
        for(ll j=0;j<newtree1[edges[i].second].size();j++){
            if(newtree1[edges[i].second][j].first==edges[i].first){ 
                newtree1[edges[i].second][j].second=peso1; 
                break; 
            }
        }
        for(ll j=0;j<newtree2[edges[i].first].size();j++){
            if(newtree2[edges[i].first][j].first==edges[i].second){ 
                newtree2[edges[i].first][j].second=peso2; 
                break; 
            }
        }
        for(ll j=0;j<newtree2[edges[i].second].size();j++){
            if(newtree2[edges[i].second][j].first==edges[i].first){ 
                newtree2[edges[i].second][j].second=peso2; 
                break; 
            }
        }
    }
    vector<vector<ll>> up1, up2;
    vector<ll> depth1, depth2, dist1, dist2;
    BLCA(newtree1,up1,depth1,dist1,r1,N,K);
    BLCA(newtree2,up2,depth2,dist2,r2,N,K);
    vector<pair<ll,ll>> questions(T);
    for(int i=0;i<T;i++){
        ll u,v;
        cin>>u>>v;
        questions[i]=mkp(u,v);
    }
    for(int i=0;i<T;i++){
        ll w1=GLCA(up1,depth1,questions[i].first,questions[i].second);
        ll w2=GLCA(up2,depth2,questions[i].first,questions[i].second);
        ll ans1=dist1[questions[i].first]+dist1[questions[i].second]-2*dist1[w1];
        ll ans2=dist2[questions[i].first]+dist2[questions[i].second]-2*dist2[w2];
        cout<<ans1<<" "<<ans2<<"\n";
    }
    cout<<flush;
    fflush(stdout);
}

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