Submission #836504

#	Time	Username	Problem	Language	Result	Execution time	Memory
836504		elkernos	Prize (CEOI22_prize)	C++17	100 / 100	2031 ms	389416 KiB

Main

// clang-format off
#include <bits/stdc++.h>
// #include <ext/pb_ds/assoc_container.hpp>
// #include <ext/pb_ds/tree_policy.hpp>
using namespace std;
// using namespace __gnu_pbds;
// template <typename T> using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
#define sim template < class c
#define ris return * this
#define dor > debug & operator <<
#define eni(x) sim > typename enable_if<sizeof dud<c>(0) x 1, debug&>::type operator<<(c i) {
sim > struct rge { c b, e; };
sim > rge<c> range(c i, c j) { return rge<c>{i, j}; }
sim > auto dud(c* x) -> decltype(cerr << *x, 0);
sim > char dud(...);
struct debug {
#ifdef XOX
~debug() { cerr << endl; }
eni(!=) cerr << boolalpha << i; ris; }
eni(==) ris << range(begin(i), end(i)); }
sim, class b dor(pair < b, c > d) { ris << "(" << d.first << ", " << d.second << ")"; }
sim dor(rge<c> d) { *this << "["; for (auto it = d.b; it != d.e; ++it) *this << ", " + 2 * (it == d.b) << *it; ris << "]"; }
#else
sim dor(const c&) { ris; }
#endif
};
#define imie(...) " [" << #__VA_ARGS__ ": " << (__VA_ARGS__) << "] "
struct { template <class T> operator T() { T x; cin >> x; return x; } } in;
#define endl '\n'
#define pb emplace_back
#define vt vector
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()
using i64 = long long;
// #define int long long
// clang-format on

const int nax = 1e6 + 7;

struct Tree {
    vector<int> g[nax];
    vector<pair<int, int>> gp[nax];
    int par[20][nax], dep[nax], real_dep[nax];
    int tin[nax], tout[nax];
    int timer;
    int root;
    void init(vector<int> p) {
        int n = (int)p.size();
        for(int i = 1; i < n; i++) {
            if(p[i] == -1) {
                root = i;
                par[0][i] = i;
            }
            else {
                par[0][i] = p[i];
                g[p[i]].push_back(i);
            }
        }
        for(int i = 1; i < 20; i++)
            for(int j = 1; j < n; j++)
                par[i][j] = par[i - 1][ par[i - 1][j] ];
        dfs(root);
    }
    void dfs(int u) {
        tin[u] = ++timer;
        for(int to : g[u]) {
            dep[to] = dep[u] + 1;
            dfs(to);
        }
        tout[u] = timer;
    }
    int lca(int u, int v) {
        if(dep[u] > dep[v]) swap(u, v);
        int delta = dep[v] - dep[u];
        for(int i = 0; delta; i++) {
            if(delta % 2) v = par[i][v];
            delta /= 2;
        }
        if(u == v) return u;
        for(int i = 19; i >= 0; i--) {
            if(par[i][u] != par[i][v]) {
                u = par[i][u];
                v = par[i][v];
            }
        }
        return par[0][u];
    }
    int dist(int a, int b) {
        debug() << imie(real_dep[a]) imie(real_dep[b]);
        return real_dep[a] + real_dep[b] - 2 * real_dep[lca(a, b)];
    }
    void wsadz(int a, int b, int da, int db) {
        int l = lca(a, b);
        if(a != l) gp[l].emplace_back(a, da), gp[a].emplace_back(l, -da);
        if(b != l) gp[l].emplace_back(b, db), gp[b].emplace_back(l, -db);
    }
    bool vis[nax];
    void licz() {
        pair<int, int> p = {1e9, -1};
        for(int i = 1; i < nax; i++) if(gp[i].size())
            p = min(p, {dep[i], i});
        queue<int> q;
        q.push(p.second);
        debug() << imie(p);
        while(q.size()) {
            int u = q.front();
            q.pop();
            debug() << imie(u) imie(gp[u]);
            for(auto [to, wei] : gp[u]) {
                real_dep[to] = real_dep[u] + wei;
                if(!vis[to]) vis[to] = 1, q.push(to);
            }
        }
    }
};

Tree tree[2];

int32_t main()
{
    cin.tie(0)->sync_with_stdio(0);
    int n = in, k = in, t = in, q = in;
    vector<vector<int>> par(2, vector<int>(n + 1));
    for(int r : {0, 1})
        for(int i = 1; i <= n; i++) par[r][i] = in;
    for(int i : {0, 1}) tree[i].init(par[i]);
    vector<int> chosen;
    queue<int> que;
    que.push(tree[0].root);
    while((int)chosen.size() != k) {
        int u = que.front();
        que.pop();
        chosen.push_back(u);
        for(int to : tree[0].g[u]) que.push(to);
    }
    for(int i : chosen) cout << i << " ";
    cout << endl;
    sort(chosen.begin(), chosen.end(), [&](int a, int b) {
        return tree[1].tin[a] < tree[1].tin[b];
    });
    for(int i = 0; i + 1 < (int)chosen.size(); i++)
        cout << "? " << chosen[i] << " " << chosen[i + 1] << endl;
    cout << "!" << endl;
    cout.flush();
    for(int i = 0; i + 1 < (int)chosen.size(); i++) {
        int a = in, b = in, c = in, d = in;
        tree[0].wsadz(chosen[i], chosen[i + 1], a, b);
        tree[1].wsadz(chosen[i], chosen[i + 1], c, d);
    }
    for(int i : {0, 1}) tree[i].licz();
    vector<pair<int, int>> answers(q);
    for(int i = 0; i < q; i++) {
        int a = in, b = in;
        // cout << tree[0].dist(a, b) << " " << tree[1].dist(a, b) << endl;
        answers[i] = {tree[0].dist(a, b), tree[1].dist(a, b)};
    }
    for(auto [aa, ab] : answers) cout << aa << " " << ab << endl;
}

Compilation message (stderr)

Main.cpp: In function 'int32_t main()':
Main.cpp:122:25: warning: unused variable 't' [-Wunused-variable]
  122 |     int n = in, k = in, t = in, q = in;
      |                         ^

• Subtask 1: 10 / 10
• Subtask 2: 25 / 25
• Subtask 3: 19 / 19
• Subtask 4: 22 / 22
• Subtask 5: 24 / 24