oj.uz

Submission #677172

# Submission time Handle Problem Language Result Execution time Memory
677172 2023-01-02T13:41:49 Z stanislavpolyn Prize (CEOI22_prize) C++17
0 / 100
 764 ms 112880 KB 
#include <bits/stdc++.h>

#define fr(i, a, b) for (int i = (a); i <= (b); ++i)
#define rf(i, a, b) for (int i = (a); i >= (b); --i)
#define fe(x, y) for (auto& x : y)

#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define mt make_tuple

#define all(x) (x).begin(), (x).end()
#define pw(x) (1LL << (x))
#define sz(x) (int)(x).size()

using namespace std;

mt19937_64 rng(228);

#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
template <typename T>
using oset = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
#define fbo find_by_order
#define ook order_of_key

template <typename T>
bool umn(T& a, T b) {
    return a > b ? (a = b, 1) : 0;
}
template <typename T>
bool umx(T& a, T b) {
    return a < b ? (a = b, 1) : 0;
}

using ll = long long;
using ld = long double;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
template <typename T>
using ve = vector<T>;

const int N = 5e5 + 5;

int n, k, q, t;
int p1[N], p2[N];
ve<int> g1[N], g2[N];
ve<int> order;

ll dep[N];
int root;

int up[N][20];
int tin[N], tout[N];
int timer;
bool used[N];

void dfs(int v = root, int p = 0) {
    up[v][0] = p;
    fr (i, 1, 19) up[v][i] = up[up[v][i - 1]][i - 1];
    tin[v] = timer++;
    fe (to, g1[v]) {
        if (!used[to]) continue;
        dfs(to, v);
    }
    tout[v] = timer++;
}

bool isUpper(int a, int b) {
    return tin[a] <= tin[b] && tin[b] <= tout[a];
}

int getLCA(int a, int b) {
    if (isUpper(a, b)) return a;
    if (isUpper(b, a)) return b;
    rf (i, 19, 0) {
        if (up[a][i] && !isUpper(up[a][i], b)) {
            a = up[a][i];
        }
    }
    return up[a][0];
}

ll getDist(int a, int b) {
    int c = getLCA(a, b);
    assert(used[c]);
    return dep[a] + dep[b] - 2 * dep[c];
}

int main() {
#ifdef LOCAL
//    freopen("input.txt", "r", stdin);
//    freopen("output.txt", "w", stdout);
#else
//    ios::sync_with_stdio(0);
//    cin.tie(0);
#endif

    cin >> n >> k >> q >> t;

    fr (i, 1, n) {
        cin >> p1[i];
        if (p1[i] != -1) {
            g1[p1[i]].pb(i);
        } else {
            root = i;
        }
    }
    fr (i, 1, n) {
        cin >> p2[i];
        if (p2[i] != -1) {
            g2[p2[i]].pb(i);
        }
    }

    {
        ve<bool> vis(n + 1);
        queue<int> q;
        q.push(root);
        vis[root] = 1;
        while (sz(q)) {
            int v = q.front();
            q.pop();
            order.pb(v);

            fe (to, g1[v]) {
                if (!vis[to]) {
                    vis[to] = 1;
                    q.push(to);
                }
            }
        }
    }

    while (sz(order) > k) order.pop_back();

    fe (x, order) cout << x << " ";
    cout << "\n" << flush;

    fe (x, order) used[x] = 1;

    fr (i, 1, sz(order) - 1) {
        cout << "? " << order[0] << " " << order[i] << "\n" << flush;
    }
    cout << "!\n" << flush;

    fr (i, 1, sz(order) - 1) {
        ll d1, d2, d3, d4;
        cin >> d1 >> d2 >> d3 >> d4;
//        assert(d1 == d2 && d2 == d3 && d3 == d4);

        dep[order[i]] =  d1;
    }

    dfs();

    fr (i, 1, t) {
        int a, b;
        cin >> a >> b;

        cout << getDist(a, b) << "\n" << flush;
    }

    return 0;
}

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 694 ms 111612 KB Time limit exceeded (wall clock)
2 Halted 0 ms 0 KB -

Subtask #2
0 / 25.0

# Verdict Execution time Memory Grader output
1 Execution timed out 764 ms 112880 KB Time limit exceeded (wall clock)
2 Halted 0 ms 0 KB -

Subtask #3
0 / 19.0

# Verdict Execution time Memory Grader output
1 Execution timed out 509 ms 64508 KB Time limit exceeded (wall clock)
2 Halted 0 ms 0 KB -

Subtask #4
0 / 22.0

# Verdict Execution time Memory Grader output
1 Runtime error 31 ms 47972 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #5
0 / 24.0

# Verdict Execution time Memory Grader output
1 Runtime error 30 ms 47960 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -