oj.uz

답안 #1011282

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1011282 2024-06-30T08:59:08 Z Forested Prize (CEOI22_prize) C++17
35 / 100
 2193 ms 478844 KB 
#include <bits/stdc++.h>
using namespace std;
using i32 = int;
using i64 = long long;
template <typename T>
using V = vector<T>;
template <typename T>
using VV = V<V<T>>;
#define OVERRIDE4(a, b, c, d, ...) d
#define REP2(i, n) for (i32 i = 0; i < (i32)(n); ++i)
#define REP3(i, l, r) for (i32 i = (i32)(l); i < (i32)(r); ++i)
#define REP(...) OVERRIDE4(__VA_ARGS__, REP3, REP2)(__VA_ARGS__)
#define PER2(i, n) for (i32 i = (i32)(n)-1; i >= 0; --i)
#define PER3(i, l, r) for (i32 i = (i32)(r)-1; i >= (i32)(l); --i)
#define PER(...) OVERRIDE4(__VA_ARGS__, PER3, PER2)(__VA_ARGS__)
#define LEN(x) (i32) size(x)
#define ALL(x) begin(x), end(x)
template <typename T>
bool chmin(T &x, const T &y) {
    if (x > y) {
        x = y;
        return true;
    }
    return false;
}
template <typename T>
bool chmax(T &x, const T &y) {
    if (x < y) {
        x = y;
        return true;
    }
    return false;
}

struct HLD {
    VV<i32> g;
    V<i32> par, sz, dep, head, in, out;

    void dfs0(i32 v) {
        if (!g[v].empty() && g[v].front() == par[v]) {
            swap(g[v].front(), g[v].back());
        }
        for (i32 &u : g[v]) {
            if (u == par[v]) {
                continue;
            }
            par[u] = v;
            dep[u] = dep[v] + 1;
            dfs0(u);
            sz[v] += sz[u];
            if (sz[u] > sz[g[v].front()]) {
                swap(g[v].front(), u);
            }
        }
    }

    void dfs1(i32 v, i32 &t) {
        in[v] = t++;
        for (i32 u : g[v]) {
            if (u == par[v]) {
                continue;
            }
            head[u] = (u == g[v].front() ? head[v] : u);
            dfs1(u, t);
        }
        out[v] = t;
    }

    HLD(const VV<i32> &g, i32 root)
        : g(g),
          par(LEN(g), -1),
          sz(LEN(g), 1),
          dep(LEN(g), 0),
          head(LEN(g), root),
          in(LEN(g), 0),
          out(LEN(g), 0) {
        dfs0(root);
        i32 t = 0;
        dfs1(root, t);
    }

    i32 lca(i32 u, i32 v) const {
        while (u != v) {
            if (in[u] > in[v]) {
                swap(u, v);
            }
            if (head[u] == head[v]) {
                break;
            }
            v = par[head[v]];
        }
        return u;
    }
};

class UnionFindWithPotential {
    V<i32> par;
    V<i32> diff;

    i32 root(i32 v) {
        if (par[v] < 0) {
            return v;
        } else {
            i32 p = par[v];
            i32 r = root(par[v]);
            diff[v] += diff[p];
            par[v] = r;
            return r;
        }
    }

public:
    UnionFindWithPotential(i32 n) : par(n, -1), diff(n, 0) {}

    // a[u] - a[v] = x
    void unite(i32 u, i32 v, i32 x) {
        i32 ru = root(u), rv = root(v);
        if (ru == rv) {
            return;
        }
        if (-par[ru] > -par[rv]) {
            swap(ru, rv);
            swap(u, v);
            x = -x;
        }
        par[rv] += par[ru];
        par[ru] = rv;
        diff[ru] = x - diff[u] + diff[v];
    }

    // a[u] - a[v]
    i32 getd(i32 u, i32 v) {
        i32 r = root(u);
        i32 r2 = root(v);
        assert(r == r2);
        return diff[u] - diff[v];
    }
    
    void show() {
        cout << '\n';
        REP(i, LEN(par)) {
            i32 r = root(i);
            cout << r << ' ' << diff[i] << '\n';
        }
        cout << '\n';
    }
};

int main() {
    i32 n, k, q, t;
    cin >> n >> k >> q >> t;
    V<i32> t0(n), t1(n);
    REP(i, n) {
        cin >> t0[i];
        if (t0[i] > 0) {
            --t0[i];
        }
    }
    REP(i, n) {
        cin >> t1[i];
        if (t1[i] > 0) {
            --t1[i];
        }
    }
    i32 r0 = (i32)(find(ALL(t0), -1) - t0.begin());
    i32 r1 = (i32)(find(ALL(t1), -1) - t1.begin());
    VV<i32> g0(n), g1(n);
    REP(i, n) {
        if (t0[i] != -1) {
            g0[t0[i]].push_back(i);
        }
    }
    REP(i, n) {
        if (t1[i] != -1) {
            g1[t1[i]].push_back(i);
        }
    }
    HLD hld0(g0, r0), hld1(g1, r1);

    
    V<i32> st(n);
    iota(ALL(st), 0);
    {
        mt19937 mt(998);
        shuffle(ALL(st), mt);
    }
    st.resize(k);
    V<i32> ord0 = st;
    V<i32> ord1 = st;
    sort(ALL(ord0),
         [&](i32 u, i32 v) -> bool { return hld0.in[u] < hld0.in[v]; });
    sort(ALL(ord1),
         [&](i32 u, i32 v) -> bool { return hld1.in[u] < hld1.in[v]; });
    V<pair<i32, i32>> qrys;
    if (q == k - 1) {
        REP(i, k - 1) { qrys.emplace_back(ord0[i], ord0[i + 1]); }
    } else {
        REP(i, k - 1) { qrys.emplace_back(ord0[i], ord0[i + 1]); }
        REP(i, k - 1) { qrys.emplace_back(ord1[i], ord1[i + 1]); }
    }
    REP(i, k) { cout << st[i] + 1 << " \n"[i + 1 == k]; }
    for (auto [a, b] : qrys) {
        cout << "? " << a + 1 << ' ' << b + 1 << '\n';
    }
    cout << "!\n";
    cout.flush();
    using PCT = tuple<i32, i32, i32, i32>;
    V<PCT> resp(q);
    for (auto &[x, y, z, w] : resp) {
        cin >> x >> y >> z >> w;
    }
    V<pair<i32, i32>> dq(t);
    REP(i, t) {
        cin >> dq[i].first >> dq[i].second;
        --dq[i].first;
        --dq[i].second;
    }

    UnionFindWithPotential uf0(n), uf1(n);
    if (q == k - 1) {
        REP(i, k - 1) {
            auto [a, b] = qrys[i];
            i32 lca0 = hld0.lca(a, b);
            i32 lca1 = hld1.lca(a, b);
            auto [x, y, z, w] = resp[i];
            uf0.unite(a, lca0, x);
            uf0.unite(b, lca0, y);
            uf1.unite(a, lca1, z);
            uf1.unite(b, lca1, w);
        }
    } else {
        REP(i, k - 1) {
            auto [a, b] = qrys[i];
            i32 lca0 = hld0.lca(a, b);
            auto [x, y, z, w] = resp[i];
            uf0.unite(a, lca0, x);
            uf0.unite(b, lca0, y);
        }
        REP(i, k - 1) {
            auto [a, b] = qrys[k - 1 + i];
            i32 lca1 = hld1.lca(a, b);
            auto [x, y, z, w] = resp[k - 1 + i];
            uf1.unite(a, lca1, z);
            uf1.unite(b, lca1, w);
            //uf1.show();
        }
    }
    
    V<pair<i32, i32>> dans(t);
    REP(i, t) {
        auto [a, b] = dq[i];
        i32 lca0 = hld0.lca(a, b);
        i32 lca1 = hld1.lca(a, b);
        dans[i].first = uf0.getd(a, lca0) + uf0.getd(b, lca0);
        dans[i].second = uf1.getd(a, lca1) + uf1.getd(b, lca1);
    }
    REP(i, t) { cout << dans[i].first << ' ' << dans[i].second << '\n'; }
    cout.flush();
}

Subtask #1
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 814 ms 172792 KB Output is correct
2 Correct 823 ms 173680 KB Output is correct
3 Correct 667 ms 120560 KB Output is correct
4 Correct 586 ms 120516 KB Output is correct
5 Correct 619 ms 120876 KB Output is correct
6 Correct 677 ms 133364 KB Output is correct
7 Correct 641 ms 133680 KB Output is correct
8 Correct 793 ms 133400 KB Output is correct
9 Correct 601 ms 120628 KB Output is correct
10 Correct 628 ms 120936 KB Output is correct
11 Correct 613 ms 120020 KB Output is correct
12 Correct 669 ms 121068 KB Output is correct

Subtask #2
25.0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1091 ms 175628 KB Output is correct
2 Correct 883 ms 173520 KB Output is correct
3 Correct 762 ms 122228 KB Output is correct
4 Correct 854 ms 123168 KB Output is correct
5 Correct 704 ms 122372 KB Output is correct
6 Correct 709 ms 134148 KB Output is correct
7 Correct 710 ms 135476 KB Output is correct
8 Correct 771 ms 135804 KB Output is correct
9 Correct 674 ms 131924 KB Output is correct
10 Correct 685 ms 132064 KB Output is correct
11 Correct 671 ms 130220 KB Output is correct
12 Correct 838 ms 131820 KB Output is correct

Subtask #3
0 / 19.0

# 결과 실행 시간 메모리 Grader output
1 Correct 712 ms 169704 KB Output is correct
2 Correct 689 ms 169460 KB Output is correct
3 Runtime error 502 ms 237292 KB Execution killed with signal 6
4 Halted 0 ms 0 KB -

Subtask #4
0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1928 ms 339180 KB Output is correct
2 Correct 1992 ms 339168 KB Output is correct
3 Runtime error 1471 ms 474924 KB Execution killed with signal 6
4 Halted 0 ms 0 KB -

Subtask #5
0 / 24.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2004 ms 342264 KB Output is correct
2 Correct 2193 ms 341896 KB Output is correct
3 Runtime error 1569 ms 478844 KB Execution killed with signal 6
4 Halted 0 ms 0 KB -