oj.uz

Submission #662453

# Submission time Handle Problem Language Result Execution time Memory
662453 2022-11-26T09:49:32 Z fatemetmhr Prize (CEOI22_prize) C++17
10 / 100
 1534 ms 261572 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];
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

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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 755 ms 188704 KB Output is correct
2 Correct 767 ms 189232 KB Output is correct
3 Correct 568 ms 146720 KB Output is correct
4 Correct 657 ms 146696 KB Output is correct
5 Correct 541 ms 147076 KB Output is correct
6 Correct 797 ms 154952 KB Output is correct
7 Correct 782 ms 154992 KB Output is correct
8 Correct 809 ms 154824 KB Output is correct
9 Correct 573 ms 146692 KB Output is correct
10 Correct 568 ms 146940 KB Output is correct
11 Correct 485 ms 146596 KB Output is correct
12 Correct 535 ms 146868 KB Output is correct

Subtask #2
0 / 25.0

# Verdict Execution time Memory Grader output
1 Runtime error 725 ms 189064 KB Execution killed with signal 13
2 Halted 0 ms 0 KB -

Subtask #3
0 / 19.0

# Verdict Execution time Memory Grader output
1 Runtime error 566 ms 186600 KB Execution killed with signal 13
2 Halted 0 ms 0 KB -

Subtask #4
0 / 22.0

# Verdict Execution time Memory Grader output
1 Runtime error 1436 ms 259388 KB Execution killed with signal 13
2 Halted 0 ms 0 KB -

Subtask #5
0 / 24.0

# Verdict Execution time Memory Grader output
1 Runtime error 1534 ms 261572 KB Execution killed with signal 13
2 Halted 0 ms 0 KB -