oj.uz

Submission #726394

# Submission time Handle Problem Language Result Execution time Memory
726394 2023-04-18T20:47:00 Z MadokaMagicaFan Prize (CEOI22_prize) C++14
0 / 100
 3091 ms 811308 KB 
#include "bits/stdc++.h"

using namespace std;
using ll = long long;

#define sz(v)   ((int)(v).size())
#define N 1000000
#define logN 21


struct tree {
    int n;
    int r;
    int j[N+5][logN], d[N], et[N];
    ll h[N];
    vector<vector<int>> adj;
    vector<array<ll, 2>> dadj[N];
    bitset<N> vis;
    int ec;

    void
    _cheight(int i, int _d)
    {
        d[i] = _d;
        et[i] = ec++;
        for (auto x : adj[i]) {
            if (j[i][0] != x)
                _cheight(x, _d+1);
        }
    }

    void
    init(int _n, vector<int>& _p)
    {
        n = _n;
        ec = 0;
        vis = 0;
        adj.resize(n);
        assert(sz(_p) == n);
        for (int i = 0; i < n; ++i) {
            if (_p[i] == -2) {
                r = i;
                j[i][0] = i;
            } else {
                j[i][0] = _p[i];
                adj[i].push_back(_p[i]);
                adj[_p[i]].push_back(i);
            }
        }

        for (int k = 1; k < logN; ++k) {
            for (int i = 0; i < n; ++i) {
                j[i][k] = j[j[i][k-1]][k-1];
            }
        }

        _cheight(r,0);
    }

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

        for (int k = 0; k < logN; ++k) {
            if (((d[a] - d[b]) >> k) & 1)
                a = j[a][k];
        }

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

    void
    doheight(int x, ll val)
    {
        if (vis[x]) return;
        vis[x] = 1;
        h[x] = val;

        for (auto u : dadj[x])
            doheight(u[0], val + u[1]);
    }
};
tree t1, t2;
int nodes[N+2], ns;

void
dfs1(int x, int k)
{
    if (ns == k) return;
    nodes[ns++] = x;
    for (auto u : t1.adj[x]) {
        if (t1.j[x][0] != u)
            dfs1(u, k);
    }
}

int
cmp(const void *a, const void *b)
{
    return t2.et[*((int *)a)] - t2.et[*((int *)b)];
}

int
main()
{
    int n, k, q, t;
    cin >> n >> k >> q >> t;

    vector<int> p(n);
    for (int i = 0; i < n; ++i) {
        cin >> p[i]; --p[i];
    }
    t1.init(n, p);

    for (int i = 0; i < n; ++i) {
        cin >> p[i]; --p[i];
    }
    t2.init(n, p);

    dfs1(t1.r, k);
    qsort(nodes, k, sizeof *nodes, cmp);

    for (int i = 0; i < k; ++i) {
        cout << nodes[i] + 1 << ' ';
    }
    cout << '\n';

    for (int i = 0; i < k-1; ++i)
        cout << "? " << nodes[i] + 1 << ' ' << nodes[i+1] + 1 << '\n';
    cout << "!\n"; cout.flush();
    for (int i = 0; i < k-1; ++i) {
        int x, y, l;
        cin >> x >> y;
        l = t1.lca(nodes[i], nodes[i+1]);
        t1.dadj[nodes[i]].push_back({l, -x});
        t1.dadj[l].push_back({nodes[i], x});
        t1.dadj[nodes[i+1]].push_back({l, -y});
        t1.dadj[l].push_back({nodes[i+1], y});

        cin >> x >> y;
        l = t2.lca(nodes[i], nodes[i+1]);
        t2.dadj[nodes[i]].push_back({l, -x});
        t2.dadj[l].push_back({nodes[i], x});
        t2.dadj[nodes[i+1]].push_back({l, -y});
        t2.dadj[l].push_back({nodes[i+1], y});
    }

    t1.doheight(nodes[0], 0);
    t2.doheight(nodes[0], 0);
	assert(0);


    while (t--) {
        int a, b, l;
        cin >> a >> b; --a; --b;

        l = t1.lca(a, b);
        cout << t1.h[a] + t1.h[b] - 2ll * t1.h[l] << ' ';
        l = t2.lca(a, b);
        cout << t2.h[a] + t2.h[b] - 2ll * t2.h[l] << '\n';
    }
    cout.flush();
}

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 1462 ms 459340 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #2
0 / 25.0

# Verdict Execution time Memory Grader output
1 Runtime error 1591 ms 468956 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #3
0 / 19.0

# Verdict Execution time Memory Grader output
1 Runtime error 1309 ms 425384 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #4
0 / 22.0

# Verdict Execution time Memory Grader output
1 Runtime error 2769 ms 761032 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #5
0 / 24.0

# Verdict Execution time Memory Grader output
1 Runtime error 3091 ms 811308 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -