oj.uz

Submission #726576

# Submission time Handle Problem Language Result Execution time Memory
726576 2023-04-19T05:48:57 Z MadokaMagicaFan Prize (CEOI22_prize) C++14
100 / 100
 2977 ms 411480 KB 
#include "bits/stdc++.h"

using namespace std;
using ll = long long;

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


struct tree {
    int n;
    int r;
    int d[N], et[N];
    vector<array<int, logN>> j;
    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);
        j.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()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int n, k, q, t;
    cin >> n >> k >> q >> t;
    vector<array<ll, 2>> ans(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);


    for (int i = 0; i < t; ++i) {
        int a, b, l;
        cin >> a >> b; --a; --b;

        l = t1.lca(a, b);
        ans[i][0] = t1.h[a] + t1.h[b] - 2ll * t1.h[l];
        l = t2.lca(a, b);
        ans[i][1] = t2.h[a] + t2.h[b] - 2ll * t2.h[l];
    }

    for (int i = 0; i < t; ++i)
        cout << ans[i][0] << ' ' << ans[i][1] << endl;
    cout.flush();
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1319 ms 233056 KB Output is correct
2 Correct 1387 ms 237360 KB Output is correct
3 Correct 1089 ms 221268 KB Output is correct
4 Correct 1067 ms 220320 KB Output is correct
5 Correct 1129 ms 224508 KB Output is correct
6 Correct 1389 ms 224252 KB Output is correct
7 Correct 1319 ms 224272 KB Output is correct
8 Correct 1353 ms 223192 KB Output is correct
9 Correct 1092 ms 220844 KB Output is correct
10 Correct 1135 ms 223772 KB Output is correct
11 Correct 1098 ms 218548 KB Output is correct
12 Correct 1138 ms 222808 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1600 ms 237788 KB Output is correct
2 Correct 1394 ms 231296 KB Output is correct
3 Correct 1181 ms 220552 KB Output is correct
4 Correct 1255 ms 224452 KB Output is correct
5 Correct 1212 ms 221840 KB Output is correct
6 Correct 1395 ms 220736 KB Output is correct
7 Correct 1552 ms 225516 KB Output is correct
8 Correct 1572 ms 226176 KB Output is correct
9 Correct 1427 ms 226524 KB Output is correct
10 Correct 1473 ms 227840 KB Output is correct
11 Correct 1372 ms 222000 KB Output is correct
12 Correct 1400 ms 227416 KB Output is correct

Subtask #3
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 1117 ms 215256 KB Output is correct
2 Correct 1033 ms 215468 KB Output is correct
3 Correct 799 ms 202164 KB Output is correct
4 Correct 803 ms 202156 KB Output is correct
5 Correct 799 ms 201976 KB Output is correct
6 Correct 944 ms 203896 KB Output is correct
7 Correct 954 ms 203968 KB Output is correct
8 Correct 953 ms 204008 KB Output is correct
9 Correct 873 ms 204332 KB Output is correct
10 Correct 897 ms 204396 KB Output is correct
11 Correct 918 ms 204376 KB Output is correct
12 Correct 877 ms 204564 KB Output is correct

Subtask #4
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 2508 ms 386764 KB Output is correct
2 Correct 2532 ms 386860 KB Output is correct
3 Correct 1694 ms 360860 KB Output is correct
4 Correct 1741 ms 360684 KB Output is correct
5 Correct 1738 ms 360612 KB Output is correct
6 Correct 2169 ms 364644 KB Output is correct
7 Correct 2191 ms 364724 KB Output is correct
8 Correct 2157 ms 364492 KB Output is correct
9 Correct 1992 ms 365540 KB Output is correct
10 Correct 1998 ms 365436 KB Output is correct
11 Correct 2102 ms 365456 KB Output is correct
12 Correct 2108 ms 365392 KB Output is correct

Subtask #5
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 2977 ms 411480 KB Output is correct
2 Correct 2784 ms 410484 KB Output is correct
3 Correct 2134 ms 379380 KB Output is correct
4 Correct 2447 ms 385396 KB Output is correct
5 Correct 2164 ms 378068 KB Output is correct
6 Correct 2866 ms 389320 KB Output is correct
7 Correct 2496 ms 382556 KB Output is correct
8 Correct 2667 ms 386376 KB Output is correct
9 Correct 2434 ms 385904 KB Output is correct
10 Correct 2499 ms 384404 KB Output is correct
11 Correct 2512 ms 384328 KB Output is correct
12 Correct 2581 ms 387552 KB Output is correct