Submission #662453

#	Time	Username	Problem	Language	Result	Execution time	Memory
662453		fatemetmhr	Prize (CEOI22_prize)	C++17	10 / 100	1534 ms	261572 KiB

Main

// heiy ... ye rooze jadid ...

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

#define all(x) x.begin(), x.end()
#define pb     push_back
#define fi     first
#define se     second

const int maxn5 = 1e6 + 10;
const int maxnt = 1e6 + 10;
const int lg    = 22;

ll h[maxn5], ans[maxn5], dis[maxn5];
vector <pair<int, ll>> adj[maxn5];
int par[lg + 1][maxn5];
pair<int, ll> pr[maxn5], have[maxn5];
int st[maxn5], ti = 0;
vector <int> av;
bool mark[maxn5];

void dfs_lca(int v){
    st[v] = ++ti; 
    if(par[0][v] == -1)
        dis[v] = 0;
    for(int i = 1; i < lg && par[i - 1][v] != -1; i++)
        par[i][v] = par[i - 1][par[i - 1][v]];
    //cout << "aha " << v << ' ' << h[v] << ' ' << dis[v] << ' ' << par[0][v] << endl;
    for(auto [u, len] : adj[v]){
        h[u] = h[v] + 1;
        dis[u] = dis[v] + len;
        par[0][u] = v;
        dfs_lca(u);
    }
}

inline int lca(int a, int b){
    if(h[a] < h[b])
        swap(a, b);
    int d = h[a] - h[b];
    //cout << "ok " << a << ' ' << b << ' ' << d << ' ' << h[a] << ' ' << h[b] << endl;
    for(int i = 0; i < lg; i++) if((d >> i)&1)
        a = par[i][a];
    //cout << "and " << a << endl;
    if(a == b)
        return a;
    for(int i = lg - 1; i >= 0; i--) if(par[i][a] != par[i][b]){
        a = par[i][a];
        b = par[i][b];
    }
    return par[0][a];
}


int main(){
    ios_base::sync_with_stdio(false); cin.tie(0);

    int n, k, q, t; cin >> n >> k >> q >> t;
    int root;
    for(int i = 0; i < n; i++){
        int p; cin >> p;
        p--;
        if(p != -2)
            adj[p].pb({i, 1});
        else
            root = i;
    }
    for(int i = 0; i < n; i++){
        int p; cin >> p;
        p--;
    }

    memset(par, -1, sizeof par);
    dfs_lca(root);
    for(int i = 0; i < k; i++){
        cout << i + 1 << ' ';
        have[i] = {st[i], i};
    }
    cout << endl;
    sort(have, have + k);
    for(int i = 1; i < k; i++){
        cout << "? " << have[i - 1].se + 1 << ' ' << have[i].se + 1 << '\n';
    }
    cout << "!" << endl;
    for(int i = 0; i < n; i++)
        pr[i].fi = -1;
    av.clear(); av.pb(have[0].se);
    for(int i = 1; i < k; i++){
        int v = have[i - 1].se, u = have[i].se;
        int c = lca(have[i - 1].se, have[i].se);
        ll d1, d2; cin >> d1 >> d2 >> d1 >> d2;
        //cout << "its " << u << ' ' << v << ' ' << c << endl;
        mark[u] = mark[v] = mark[c] = true;
        while(av.size() && h[c] < h[av.back()]){
            v = av.back();
            av.pop_back();
            d1 -= pr[v].se;
            //cout << "pop " << v << endl;
        }
        //cout << "ok " << v << ' ' << u << ' ' << c << ' ' << d1 << endl;
        if(v != c){
            d1 += pr[v].se;
            if(av.size() && av.back() != c){
                pr[c] = {av.back(), pr[v].se - d1};
                //cout << "oh par " << pr[c].fi << ' ' << pr[c].se << endl;
            }
            if(av.empty() || av.back() != c)
                av.pb(c);
            pr[v] = {c, d1};
            //cout << "here " << d1 << endl;
        }
        if(c != u){
            av.pb(u);
            pr[u] = {c, d2};
        }
    }
    for(int i = 0; i < n; i++)
        adj[i].clear();
    for(int i = 0; i < n; i++){ 
        if(pr[i].fi != -1)
            adj[pr[i].fi].pb({i, pr[i].se});
        else if(mark[i])
            root = i;
    }
    //cout << "SECOND TREE " << endl;
    memset(par, -1, sizeof par);
    h[root] = 0;
    //return 0;
    dfs_lca(root);
    for(int i = 0; i < t; i++){
        int a, b; cin >> a >> b; a--; b--;
        int c = lca(a, b);
        ans[i] = dis[a] + dis[b] - 2 * dis[c];
    }
    for(int i = 0; i < t; i++)
        cout << ans[i] << ' ' << ans[i] << '\n';
    cout << endl;
}

/*
9 3 2 3
2 -1 2 1 1 5 1 4 5
9 4 5 5 7 3 -1 3 7


0 3 0 3
3 1 3 1

*/

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:78:12: warning: 'root' may be used uninitialized in this function [-Wmaybe-uninitialized]
   78 |     dfs_lca(root);
      |     ~~~~~~~^~~~~~

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