Submission #1194102

#	Time	Username	Problem	Language	Result	Execution time	Memory
1194102		Taxiradio	Prize (CEOI22_prize)	C++20	0 / 100	1366 ms	332964 KiB

Main

#include<iostream>
#include<vector>
#include<string>
#include<algorithm>
#include<array>
#include<set>
#include<map>
#include<queue>

using namespace std;

vector<vector<int>> g3 , g4;
vector<int> z1 , z2 ;
int l = 0;
int n , k , q , t;

void makeG(){
    cin >> n >> k >> q >> t;
    vector<int> p1 , p2;
    vector<vector<int>> g1 , g2;
    vector<int> o1 , o2;
    g1.resize(n);
    g2.resize(n);
    g3.resize(n);
    g4.resize(n);
    z1.resize(n);
    z2.resize(n);
    o1.resize(n);
    o2.resize(n);
    for(int i = 0; i < n; i++){
        int y; cin >> y;y--;
        p1.push_back(y);
        if(y >= 0)g1[y].push_back(i);
    }
    for(int i = 0; i < n; i++){
        int y; cin >> y;y--;
        p2.push_back(y);
        if(y >= 0)g2[y].push_back(i);
    }
    queue<int> a;
    vector<int> u(n , 2);
    for(int i = 0; i < n; i++){
        o1[i] = g1[i].size();
        o2[i] = g2[i].size();
        if(o1[i] <= 1)u[i]--;
        if(o2[i] <= 1)u[i]--;
        if(u[i] == 0)a.push(i);
    }
    vector<bool> b(n , 1);
    for(int i = 0; i < n-k; i++){
        int x = a.front();
        b[x] = 0;
        //cout << x << endl;
        a.pop();
        if(p1[x] < 0){
            int m = 0;
            for(int m1 : g1[x]){
                if(b[m1])m = m1;
            }
            p1[m] = p1[x];
        }else{
            o1[p1[x]]--;
            if(o1[x] == 0){
                if(o1[p1[x]] == 1){
                    u[p1[x]]--;
                    if(u[p1[x]] == 0)a.push(p1[x]);
                }
            }else{
                int m = 0;
                for(int m1 : g1[x]){
                    if(b[m1])m = m1;
                }
                g1[p1[x]].push_back(m);
                o1[p1[x]]++;
                p1[m] = p1[x];
            }
        }

        if(p2[x] < 0){
            int m = 0;
            for(int m1 : g2[x]){
                if(b[m1])m = m1;
            }
            p2[m] = p2[x];
        }else{
            o2[p2[x]]--;
            if(o2[x] == 0){
                if(o2[p2[x]] == 1){
                    u[p2[x]]--;
                    if(u[p2[x]] == 0)a.push(p2[x]);
                }
            }else{
                int m = 0;
                for(int m1 : g2[x]){
                    if(b[m1])m = m1;
                }
                o2[p2[x]]++;
                g2[p2[x]].push_back(m);
                p2[m] = p2[x];
            }
        }
    }
    for(int i = 0; i < n; i++){
        if(!b[i]) continue;
        cout << i+1 << " ";
        l = i;
        if(p1[i] >= 0)g3[i].push_back(p1[i]);
        if(p1[i] >= 0)g3[p1[i]].push_back(i);
        if(p2[i] >= 0)g4[i].push_back(p2[i]);
        if(p2[i] >= 0)g4[p2[i]].push_back(i);
    }
    cout << endl;
    for(int i = 0; i < n; i++){
        if(!b[i] || i == l) continue;
        cout << "? " << i+1 << " " << l+1 << "\n";
    }
    cout << "!" << endl;
    for(int i = 0; i < n; i++){
        if(!b[i] || i == l) continue;
        int v1 , v2 , v3 , v4; cin >> v1 >> v2 >> v3 >> v4;
        z1[i] = v1+v2;
        z2[i] = v3+v4;
    }
}

vector<array<int , 25>> b1 , b2;
vector<int> d1 , d2;

void bl1(int h , int p){
    if(p == -1)d1[h] = 0;else d1[h] = d1[p]+1;
    b1[h][0] = p;
    for(int i = 1; i < 25; i++){
        if(b1[h][i-1] == -1){
            b1[h][i] = -1;
        }else{
            b1[h][i] = b1[b1[h][i-1]][i-1];
        }
    }
    for(int x : g3[h]){
        if(x != p)bl1(x , h);
    }
}

void bl2(int h , int p){
    if(p == -1)d2[h] = 0;else d2[h] = d2[p]+1;
    b2[h][0] = p;
    for(int i = 1; i < 25; i++){
        if(b2[h][i-1] == -1){
            b2[h][i] = -1;
        }else{
            b2[h][i] = b2[b2[h][i-1]][i-1];
        }
    }
    for(int x : g4[h]){
        if(x != p)bl2(x , h);
    }
}

int lca1(int a1 , int a2){
    if(d1[a1] < d1[a2])swap(a1 , a2);
    for(int i = 24; i >= 0; i--){
        if((d1[a1]-d1[a2])&(1<<i)){
            a1 = b1[a1][i];
        }
    }
    if(a1 == a2)return a1;
    for(int i = 24; i >= 0; i--){
        if(b1[a1][i] != b1[a2][i]){
            a1 = b1[a1][i];
            a2 = b1[a2][i];
        }
    }
    return b1[a1][0];
}

int lca2(int a1 , int a2){
    if(d2[a1] < d2[a2])swap(a1 , a2);
    for(int i = 24; i >= 0; i--){
        if((d2[a1]-d2[a2])&(1<<i)){
            a1 = b2[a1][i];
        }
    }
    if(a1 == a2)return a1;
    for(int i = 24; i >= 0; i--){
        if(b2[a1][i] != b2[a2][i]){
            a1 = b2[a1][i];
            a2 = b2[a2][i];
        }
    }
    return b2[a1][0];
}

int32_t main(){
    makeG();
    d1.resize(n);
    d2.resize(n);
    b1.resize(n);
    b2.resize(n);
    bl1(l , -1);
    bl2(l , -1);
    while(t--){
        int x1 , x2; cin >> x1 >> x2;x1--;x2--;
        cout << z1[x1]+z1[x2]-2*z1[lca1(x1 , x2)] << " " << z2[x1]+z2[x2]-2*z2[lca2(x1 , x2)] << "\n";
    }
    cout << endl;
}

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