Submission #662499

# Submission time Handle Problem Language Result Execution time Memory
662499 2022-11-26T10:16:09 Z fatemetmhr Prize (CEOI22_prize) C++17
29 / 100
3500 ms 406952 KB
// 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

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);
      |     ~~~~~^~~~~~~~~~~~~~~~
# Verdict Execution time Memory Grader output
1 Correct 1781 ms 292824 KB Output is correct
2 Correct 1645 ms 294116 KB Output is correct
3 Correct 1091 ms 235808 KB Output is correct
4 Correct 1048 ms 235500 KB Output is correct
5 Correct 1178 ms 236748 KB Output is correct
6 Correct 1717 ms 248280 KB Output is correct
7 Correct 1773 ms 248332 KB Output is correct
8 Correct 1802 ms 247848 KB Output is correct
9 Correct 1157 ms 235776 KB Output is correct
10 Correct 1131 ms 236360 KB Output is correct
11 Correct 1090 ms 235032 KB Output is correct
12 Correct 1195 ms 236164 KB Output is correct
# Verdict Execution time Memory Grader output
1 Runtime error 570 ms 133924 KB Execution killed with signal 13
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Correct 1565 ms 288224 KB Output is correct
2 Correct 1569 ms 288408 KB Output is correct
3 Correct 859 ms 239220 KB Output is correct
4 Correct 903 ms 239312 KB Output is correct
5 Correct 883 ms 239488 KB Output is correct
6 Correct 1292 ms 249156 KB Output is correct
7 Correct 1313 ms 249180 KB Output is correct
8 Correct 1372 ms 249168 KB Output is correct
9 Correct 1111 ms 248056 KB Output is correct
10 Correct 1146 ms 248100 KB Output is correct
11 Correct 1276 ms 248076 KB Output is correct
12 Correct 1186 ms 248012 KB Output is correct
# Verdict Execution time Memory Grader output
1 Execution timed out 3580 ms 406952 KB Time limit exceeded
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Runtime error 1250 ms 187536 KB Execution killed with signal 13
2 Halted 0 ms 0 KB -