Submission #662499

#	Time	Username	Problem	Language	Result	Execution time	Memory
662499		fatemetmhr	Prize (CEOI22_prize)	C++17	29 / 100	3580 ms	406952 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], out[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, adj1[maxn5], adj2[maxn5];  
bool mark[maxn5];
int st1[maxn5], st2[maxn5], ti1 = 0, ti2 = 0;
ll dd1[maxn5], dd2[maxn5], dd3[maxn5], dd4[maxn5];
int q1[maxn5], q2[maxn5], dp1[maxn5], dp2[maxn5], last1[maxn5], last2[maxn5];
int pre1[maxn5], pre2[maxn5], a[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];
}

inline void solve(int n, int k, int t, int root){
    memset(par, -1, sizeof par);
    memset(mark, false, sizeof mark);
    ti = 0;
    h[root] = dis[root] = 0;
    dfs_lca(root);
    for(int i = 0; i < n; i++){
        pr[i].fi = -1;
        pr[i].se = 0;
    }
    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 = dd1[i], d2 = dd2[i];
        //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 = q1[i], b = q2[i];
        int c = lca(a, b);
        ans[i] = dis[a] + dis[b] - 2 * dis[c];
    }
}

void dfs_st2(int v){
    st2[v] = ti2++;
    for(auto u : adj2[v])
        dfs_st2(u);
}

void dfs_st1(int v){
    st1[v] = ti1++;
    for(auto u : adj1[v])
        dfs_st1(u);
}

inline bool cmp(int i, int j){return st1[i] < st1[j];}


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

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

    dfs_st1(root1);
    dfs_st2(root2);

    for(int i = 0; i < n; i++)
        a[i] = i;
    sort(a, a + n, cmp); // bar hasbe st1
    fill(dp1, dp1 + n + 5, 1e9);
    fill(dp2, dp2 + n + 5, 1e9);
    int ans1 = 0, ans2 = 0;
    int good1, good2;
    memset(last1, -1, sizeof last1);
    memset(last2, -1, sizeof last2);
    for(int i = 0; i < n; i++){
        int p1 = lower_bound(dp1 + 1, dp1 + n + 3, st2[a[i]]) - dp1;
        int p2 = lower_bound(dp2 + 1, dp2 + n + 3, -st2[a[i]]) - dp2;
        pre1[i] = last1[p1 - 1];
        pre2[i] = last2[p2 - 1];
        dp1[p1] = st2[a[i]];
        dp2[p2] = -st2[a[i]];
        last1[p1] = last2[p2] = i;
        if(p1 > ans1){
            good1 = i;
            ans1 = p1;
        }
        if(p2 > ans2){
            good2 = i;
            ans2 = p2;
        }
    }

    //cout << "ok " << ans1 << ' ' << ans2 << endl;

    if(ans1 > ans2){
        int v = good1;
        for(int i = 0; i < k; i++){
            have[i] = {0, a[v]};
            v = pre1[v];
        }
    }
    else{
        int v = good2;
        for(int i = 0; i < k; i++){
            have[i] = {0, a[v]};
            v = pre2[v];
        }
    }

    for(int i = 0; i < k; i++){
        cout << have[i].se + 1 << ' ';
    }
    cout << endl;
    for(int i = 1; i < k; i++){
        cout << "? " << have[i - 1].se + 1 << ' ' << have[i].se + 1 << '\n';
    }
    cout << "!" << endl;
    for(int i = 1; i < k; i++)
        cin >> dd1[i] >> dd2[i] >> dd3[i] >> dd4[i];
    for(int i = 0; i < t; i++){
        cin >> q1[i] >> q2[i];
        q1[i]--; q2[i]--;
    }
    for(int i = 0; i < n; i++){
        adj[i].clear();
        for(auto u : adj1[i])
            adj[i].pb({u, 1});
    }
    solve(n, k, t, root1);
    for(int i = 0; i < t; i++)
        out[i] = ans[i];
    for(int i = 0; i < n; i++){
        adj[i].clear();
        for(auto u : adj2[i])
            adj[i].pb({u, 1});
    }
    for(int i = 1; i < k; i++){
        swap(dd1[i], dd3[i]);
        swap(dd2[i], dd4[i]);
    }
    solve(n, k, t, root2);
    for(int i = 0; i < t; i++)
        cout << out[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:202:15: warning: 'good2' may be used uninitialized in this function [-Wmaybe-uninitialized]
  202 |             v = pre2[v];
      |             ~~^~~~~~~~~
Main.cpp:195:15: warning: 'good1' may be used uninitialized in this function [-Wmaybe-uninitialized]
  195 |             v = pre1[v];
      |             ~~^~~~~~~~~
Main.cpp:225:10: warning: 'root1' may be used uninitialized in this function [-Wmaybe-uninitialized]
  225 |     solve(n, k, t, root1);
      |     ~~~~~^~~~~~~~~~~~~~~~
Main.cpp:237:10: warning: 'root2' may be used uninitialized in this function [-Wmaybe-uninitialized]
  237 |     solve(n, k, t, root2);
      |     ~~~~~^~~~~~~~~~~~~~~~

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