Submission #727496

#	Time	Username	Problem	Language	Result	Execution time	Memory
727496		bitaro1337	Prize (CEOI22_prize)	C++17	100 / 100	3231 ms	452404 KiB

Main

//BITARO BITARO BITARO
#include <bits/stdc++.h>
using namespace std;
const int K = 20, N = 1e6 + 5;
int jump[2][N][K], depth[2][N], time_in[2][N], dist[2][N], vis[2][N], tt[2], root[2];
vector<int> g[2][N];
vector<pair<int, int>> adj[2][N];
void dfs(int t, int u) {
    time_in[t][u] = tt[t]++;
    for(int j = 1; j < K; ++j) {
        jump[t][u][j] = jump[t][jump[t][u][j - 1]][j - 1];
    }
    for(int v: g[t][u]) {
        jump[t][v][0] = u;
        depth[t][v] = depth[t][u] + 1;
        dfs(t, v);
    }
}
void get_distances(int t, int u) {
    vis[t][u] = 1;
    for(auto x: adj[t][u]) {
        int v = x.first, w = x.second;
        if(vis[t][v]) continue;
        dist[t][v] = dist[t][u] + w;
        get_distances(t, v);
    }
}
int lca(int t, int a, int b) {
    if(depth[t][a] < depth[t][b]) swap(a, b);
    for(int j = K - 1; j >= 0; --j) {
        if(jump[t][a][j] && depth[t][jump[t][a][j]] >= depth[t][b]) {
            a = jump[t][a][j];
        }
    }
    if(a == b) return a;
    for(int j = K - 1; j >= 0; --j) {
        if(jump[t][a][j] && jump[t][b][j] && jump[t][a][j] != jump[t][b][j]) {
            a = jump[t][a][j];
            b = jump[t][b][j];
        }
    }
    return jump[t][a][0];
}
int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int n, k, q, T; cin >> n >> k >> q >> T;
    for(int t = 0; t < 2; ++t) {
        for(int i = 1; i <= n; ++i) {
            int p; cin >> p;
            if(p == -1) root[t] = i;
            else g[t][p].push_back(i);
        }
        dfs(t, root[t]);
    }
    vector<int> nodes(n); iota(nodes.begin(), nodes.end(), 1);
    sort(nodes.begin(), nodes.end(), [&](int i, int j){return time_in[0][i] < time_in[0][j];});
    while(nodes.size() > k) nodes.pop_back();
    if(time_in[0][root[1]] >= k) {
        nodes.pop_back();
        nodes.push_back(root[1]);
    }
    sort(nodes.begin(), nodes.end(), [&](int i, int j){return time_in[1][i] < time_in[1][j];});
    for(int x: nodes) cout << x << " ";
    cout << "\n"; cout.flush();
    for(int i = 0; i + 1 < k; ++i) cout << "? " << nodes[i] << " " << nodes[i + 1] << "\n";
    cout << "!\n"; cout.flush();

    for(int i = 0; i + 1 < k; ++i) {
        for(int t = 0; t < 2; ++t) {
            int u = nodes[i], v = nodes[i + 1];
            int l = lca(t, u, v);
            int c1, c2; cin >> c1 >> c2;
            adj[t][l].push_back({u, c1});
            adj[t][u].push_back({l, -c1});
            adj[t][l].push_back({v, c2});
            adj[t][v].push_back({l, -c2});
        }
    }
    get_distances(0, root[0]);
    get_distances(1, root[1]);
    vector<pair<int, int>> Q(T);
    for(int i = 0; i < T; ++i) {
        cin >> Q[i].first >> Q[i].second;
    }
    for(int i = 0; i < T; ++i) {
        int u = Q[i].first, v = Q[i].second;
        for(int t = 0; t < 2; ++t) {
            cout << dist[t][u] + dist[t][v] - 2 * dist[t][lca(t, u, v)] << " ";
        }
        cout << "\n";
    }
    cout.flush();
}

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:58:24: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   58 |     while(nodes.size() > k) nodes.pop_back();
      |           ~~~~~~~~~~~~~^~~

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