oj.uz

Submission #726904

# Submission time Handle Problem Language Result Execution time Memory
726904 2023-04-19T14:02:12 Z MadokaMagicaFan Prize (CEOI22_prize) C++14
10 / 100
 1648 ms 294268 KB 
#include "bits/stdc++.h"

using namespace std;

using ll = long long;
using vi = vector<int>;
using pi = pair<int, int>;

#define forn(i,n)       for(int i = 0; i < n; ++i)
#define forr(i,n)       for(int i = n-1; i >= 0; --i)
#define forbe(i,b,e)    for(int i = b; i < e; ++i)

#define all(v)          (v).begin(),(v).end()
#define sort(v)         sort(all(v))
#define sz(v)           ((int)(v).size())

#define endl '\n';

#define pb              push_back
#define ONPC

const int N = 1e6;
const int K = 20;
int cnt = 0;

int n, k, q, t;

vi sv;

using a4 = array<int,4>;

int query(int a, int b){
    cout << "? " << a << ' ' << b << endl;
    return cnt++;
}

struct tree{
    // TODO vectors
    vi p;
    vector<array<int,K>> j;
    vi d;
    vi dep;
    vector<vi> adj;
    int root;
    int n;
    bitset<N> s;
    
    tree(int _n) {
        n = _n;
        p.assign(n+3,0);
        d.assign(n+3,0);
        dep.assign(n+3,0);
        j.resize(n+3);
        adj.assign(n+3,{});
        s = 0;
    }

    void
    build()
    {
        forbe(i,1,n){
            if (p[i] == -1) {
                p[i] = i;
                root = i;
                break;
            }
        }
        forbe(i,1,n){
            if (i == root) continue;
            adj[p[i]].pb(i);
            adj[i].pb(p[i]);
        }
    }


    int
    dfs(int i, int k, int par)
    {
        if (k == 0) return 0;
        s[i] = 1;
        --k;
        sv.pb(i);
        if (k == 0) return 0;

        for (int u : adj[i]) {
            if (u == par) continue;
            dep[u] = dep[i]+1;
            k = dfs(u, k, i);
            if (!k) return 0;
        }

        return k;
    }

    void
    ask(int i, int par) {
        if (!s[i]) return;
        j[i][0] = p[i];
        if (i != root) {
            d[i] = query(i,par);
        }

        for (int u : adj[i]) {
            if (u == par) continue;
            ask(u,i);
        }
    }

    void
    dfs2(int i, int par) {
        if (!s[i]) return;
        if (i != root)
            d[i] += d[p[i]];
        for (int u : adj[i]) {
            if (u != par) dfs2(u, i);
        }
    }

    void 
    build(vi& dist)
    {
        forn(i, n) {
            if (i == root) continue;
            if (!s[i]) continue;
            d[i] = dist[d[i]];
        }

        dfs2(root, root);

        forbe(k,1, K) {
            forn(i, n) {
                if (s[i]) j[i][k] = j[j[i][k-1]][k-1];
            }
        }
    }

    int
    lca(int a, int b){
        if (dep[a] < dep[b]) swap(a,b);

        for(int k = K-1; k >= 0; --k) {
            if (dep[j[a][k]] >= dep[b])
                a = j[a][k];
        }

        if (a == b) return b;


        for(int k = K-1; k >= 0; --k) {
            if (j[a][k] != j[b][k]) {
                a = j[a][k];
                b = j[b][k];
            }
        }

        return j[a][0];
    }

    int
    dist(int a, int b)
    {
        ll d1 = d[a];
        ll d2 = d[b];
        d1 += d2;
        
        a = lca(a,b);

        d2 = d[a];
        d2 *= 2l;
        d1 -= d2;

        return d1;
    }
};

#ifdef ONPC
void
solve() {
    cin >> n >> k >> q >> t;
    tree t1(n+1), t2(n+1);
    forn(i, n) cin >> t1.p[i+1];
    forn(i, n) cin >> t2.p[i+1];
    int a, b;

    t1.build();
    t2.build();

    t1.dfs(t1.root, k, t1.root); 
    forn(i, k) cout << sv[i] << ' ';
    cout << endl;

    t1.ask(t1.root, t1.root); 
    cout << "!" << endl;
    cout.flush();

    vi dist(cnt);
    forn(i, cnt) {
        cin >> dist[i] >> a >> b;
        cin >> b;
        dist[i] = max(dist[i],a);
    }

    t1.build(dist);

    vi ans(t);
    forn(i, t) {
        cin >> a >> b;
        ans[i] = t1.dist(a,b);
    }

    forn(i,t) cout << ans[i] << ' ' << ans[i] << endl;
    cout.flush();
}

int32_t
main(int argc, char** argv) {
    if (argc > 1)
        freopen(argv[1],"r", stdin);
    solve();
}
#endif

Compilation message

Main.cpp: In function 'int32_t main(int, char**)':
Main.cpp:218:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  218 |         freopen(argv[1],"r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1071 ms 148460 KB Output is correct
2 Correct 1167 ms 149508 KB Output is correct
3 Correct 943 ms 147704 KB Output is correct
4 Correct 925 ms 147784 KB Output is correct
5 Correct 994 ms 147996 KB Output is correct
6 Correct 1049 ms 147584 KB Output is correct
7 Correct 1115 ms 147612 KB Output is correct
8 Correct 1087 ms 147436 KB Output is correct
9 Correct 910 ms 147612 KB Output is correct
10 Correct 929 ms 147808 KB Output is correct
11 Correct 903 ms 147640 KB Output is correct
12 Correct 1051 ms 147668 KB Output is correct

Subtask #2
0 / 25.0

# Verdict Execution time Memory Grader output
1 Runtime error 999 ms 149372 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 592 ms 145656 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 1524 ms 290772 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 1648 ms 294268 KB Execution killed with signal 13
2 Halted 0 ms 0 KB -