oj.uz

Submission #836504

# Submission time Handle Problem Language Result Execution time Memory
836504 2023-08-24T12:02:01 Z elkernos Prize (CEOI22_prize) C++17
100 / 100
 2031 ms 389416 KB 
// 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

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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 984 ms 243940 KB Output is correct
2 Correct 972 ms 245748 KB Output is correct
3 Correct 798 ms 217364 KB Output is correct
4 Correct 719 ms 216748 KB Output is correct
5 Correct 757 ms 218996 KB Output is correct
6 Correct 1083 ms 223648 KB Output is correct
7 Correct 959 ms 223684 KB Output is correct
8 Correct 957 ms 223128 KB Output is correct
9 Correct 711 ms 217144 KB Output is correct
10 Correct 788 ms 218676 KB Output is correct
11 Correct 637 ms 215808 KB Output is correct
12 Correct 726 ms 218168 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1061 ms 245704 KB Output is correct
2 Correct 956 ms 243032 KB Output is correct
3 Correct 822 ms 218136 KB Output is correct
4 Correct 881 ms 220272 KB Output is correct
5 Correct 859 ms 218664 KB Output is correct
6 Correct 1041 ms 222964 KB Output is correct
7 Correct 1161 ms 225900 KB Output is correct
8 Correct 1231 ms 226036 KB Output is correct
9 Correct 1028 ms 224372 KB Output is correct
10 Correct 1076 ms 225084 KB Output is correct
11 Correct 1059 ms 221728 KB Output is correct
12 Correct 1053 ms 224892 KB Output is correct

Subtask #3
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 622 ms 237936 KB Output is correct
2 Correct 637 ms 237884 KB Output is correct
3 Correct 488 ms 209268 KB Output is correct
4 Correct 466 ms 209180 KB Output is correct
5 Correct 493 ms 209264 KB Output is correct
6 Correct 605 ms 216060 KB Output is correct
7 Correct 650 ms 216052 KB Output is correct
8 Correct 601 ms 216092 KB Output is correct
9 Correct 573 ms 214168 KB Output is correct
10 Correct 574 ms 213968 KB Output is correct
11 Correct 594 ms 213888 KB Output is correct
12 Correct 540 ms 214032 KB Output is correct

Subtask #4
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 1504 ms 383432 KB Output is correct
2 Correct 1518 ms 383580 KB Output is correct
3 Correct 1055 ms 326068 KB Output is correct
4 Correct 1165 ms 326096 KB Output is correct
5 Correct 1086 ms 326080 KB Output is correct
6 Correct 1341 ms 339680 KB Output is correct
7 Correct 1379 ms 339928 KB Output is correct
8 Correct 1428 ms 339716 KB Output is correct
9 Correct 1393 ms 335672 KB Output is correct
10 Correct 1201 ms 335564 KB Output is correct
11 Correct 1184 ms 335588 KB Output is correct
12 Correct 1185 ms 335608 KB Output is correct

Subtask #5
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 1968 ms 389416 KB Output is correct
2 Correct 2031 ms 389060 KB Output is correct
3 Correct 1313 ms 332032 KB Output is correct
4 Correct 1405 ms 336516 KB Output is correct
5 Correct 1301 ms 331392 KB Output is correct
6 Correct 1922 ms 348668 KB Output is correct
7 Correct 1769 ms 344648 KB Output is correct
8 Correct 1889 ms 347144 KB Output is correct
9 Correct 1758 ms 342976 KB Output is correct
10 Correct 1583 ms 341896 KB Output is correct
11 Correct 1613 ms 341828 KB Output is correct
12 Correct 1605 ms 343956 KB Output is correct