oj.uz

Submission #836501

# Submission time Handle Problem Language Result Execution time Memory
836501 2023-08-24T12:00:16 Z elkernos Prize (CEOI22_prize) C++17
100 / 100
 2153 ms 389420 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;
    cout.flush();
    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;
        answers[i] = {tree[0].dist(a, b), tree[1].dist(a, b)};
    }
    for(auto [aa, ab] : answers) cout << aa << " " << ab << endl;
    cout.flush();
}

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 784 ms 243848 KB Output is correct
2 Correct 829 ms 245744 KB Output is correct
3 Correct 659 ms 217384 KB Output is correct
4 Correct 620 ms 216720 KB Output is correct
5 Correct 660 ms 219096 KB Output is correct
6 Correct 893 ms 223692 KB Output is correct
7 Correct 857 ms 223604 KB Output is correct
8 Correct 843 ms 223128 KB Output is correct
9 Correct 620 ms 217148 KB Output is correct
10 Correct 651 ms 218652 KB Output is correct
11 Correct 634 ms 215816 KB Output is correct
12 Correct 701 ms 218208 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 961 ms 245636 KB Output is correct
2 Correct 865 ms 242948 KB Output is correct
3 Correct 707 ms 218168 KB Output is correct
4 Correct 754 ms 220384 KB Output is correct
5 Correct 711 ms 218672 KB Output is correct
6 Correct 1047 ms 222936 KB Output is correct
7 Correct 1102 ms 225784 KB Output is correct
8 Correct 1037 ms 226040 KB Output is correct
9 Correct 985 ms 224364 KB Output is correct
10 Correct 1006 ms 225084 KB Output is correct
11 Correct 905 ms 221728 KB Output is correct
12 Correct 937 ms 225052 KB Output is correct

Subtask #3
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 555 ms 237936 KB Output is correct
2 Correct 572 ms 238016 KB Output is correct
3 Correct 404 ms 209324 KB Output is correct
4 Correct 401 ms 209232 KB Output is correct
5 Correct 405 ms 209344 KB Output is correct
6 Correct 539 ms 216268 KB Output is correct
7 Correct 535 ms 216084 KB Output is correct
8 Correct 562 ms 216088 KB Output is correct
9 Correct 555 ms 213940 KB Output is correct
10 Correct 520 ms 213972 KB Output is correct
11 Correct 512 ms 213916 KB Output is correct
12 Correct 469 ms 214096 KB Output is correct

Subtask #4
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 1542 ms 383564 KB Output is correct
2 Correct 1587 ms 383584 KB Output is correct
3 Correct 992 ms 326064 KB Output is correct
4 Correct 957 ms 326156 KB Output is correct
5 Correct 1029 ms 326076 KB Output is correct
6 Correct 1337 ms 339716 KB Output is correct
7 Correct 1371 ms 339932 KB Output is correct
8 Correct 1419 ms 339728 KB Output is correct
9 Correct 1437 ms 335592 KB Output is correct
10 Correct 1242 ms 335568 KB Output is correct
11 Correct 1350 ms 335564 KB Output is correct
12 Correct 1381 ms 335548 KB Output is correct

Subtask #5
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 2153 ms 389420 KB Output is correct
2 Correct 2029 ms 389064 KB Output is correct
3 Correct 1494 ms 332040 KB Output is correct
4 Correct 1447 ms 336516 KB Output is correct
5 Correct 1289 ms 331380 KB Output is correct
6 Correct 1934 ms 348596 KB Output is correct
7 Correct 1780 ms 344656 KB Output is correct
8 Correct 1908 ms 347144 KB Output is correct
9 Correct 1663 ms 342856 KB Output is correct
10 Correct 1633 ms 341852 KB Output is correct
11 Correct 1651 ms 341840 KB Output is correct
12 Correct 1832 ms 343964 KB Output is correct