Submission #726904

#	Time	Username	Problem	Language	Result	Execution time	Memory
726904		MadokaMagicaFan	Prize (CEOI22_prize)	C++14	10 / 100	1648 ms	294268 KiB

Main

#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 (stderr)

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 / 10
• Subtask 2: 0 / 25
• Subtask 3: 0 / 19
• Subtask 4: 0 / 22
• Subtask 5: 0 / 24