oj.uz

Submission #727496

# Submission time Handle Problem Language Result Execution time Memory
727496 2023-04-20T21:17:06 Z bitaro1337 Prize (CEOI22_prize) C++17
100 / 100
 3231 ms 452404 KB 
//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

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

# Verdict Execution time Memory Grader output
1 Correct 1558 ms 275424 KB Output is correct
2 Correct 1619 ms 277840 KB Output is correct
3 Correct 980 ms 214304 KB Output is correct
4 Correct 996 ms 213928 KB Output is correct
5 Correct 1026 ms 216288 KB Output is correct
6 Correct 1460 ms 227844 KB Output is correct
7 Correct 1492 ms 227908 KB Output is correct
8 Correct 1439 ms 227272 KB Output is correct
9 Correct 1020 ms 214172 KB Output is correct
10 Correct 1056 ms 215860 KB Output is correct
11 Correct 954 ms 212916 KB Output is correct
12 Correct 997 ms 215400 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1819 ms 278092 KB Output is correct
2 Correct 1727 ms 274272 KB Output is correct
3 Correct 1099 ms 214360 KB Output is correct
4 Correct 1153 ms 216636 KB Output is correct
5 Correct 1067 ms 215056 KB Output is correct
6 Correct 1544 ms 226244 KB Output is correct
7 Correct 1660 ms 228928 KB Output is correct
8 Correct 1788 ms 229184 KB Output is correct
9 Correct 1548 ms 227060 KB Output is correct
10 Correct 1601 ms 227912 KB Output is correct
11 Correct 1457 ms 224520 KB Output is correct
12 Correct 1593 ms 227720 KB Output is correct

Subtask #3
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 1077 ms 263716 KB Output is correct
2 Correct 1105 ms 263808 KB Output is correct
3 Correct 714 ms 202196 KB Output is correct
4 Correct 734 ms 202480 KB Output is correct
5 Correct 735 ms 202264 KB Output is correct
6 Correct 903 ms 215076 KB Output is correct
7 Correct 899 ms 215196 KB Output is correct
8 Correct 916 ms 215236 KB Output is correct
9 Correct 845 ms 213212 KB Output is correct
10 Correct 847 ms 212940 KB Output is correct
11 Correct 883 ms 212916 KB Output is correct
12 Correct 863 ms 213140 KB Output is correct

Subtask #4
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 2945 ms 437864 KB Output is correct
2 Correct 2493 ms 437956 KB Output is correct
3 Correct 1618 ms 315448 KB Output is correct
4 Correct 1588 ms 315236 KB Output is correct
5 Correct 1606 ms 315244 KB Output is correct
6 Correct 2102 ms 340876 KB Output is correct
7 Correct 2116 ms 341160 KB Output is correct
8 Correct 2216 ms 340788 KB Output is correct
9 Correct 1955 ms 337056 KB Output is correct
10 Correct 1947 ms 336836 KB Output is correct
11 Correct 2021 ms 336636 KB Output is correct
12 Correct 1923 ms 336684 KB Output is correct

Subtask #5
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 3231 ms 452404 KB Output is correct
2 Correct 3226 ms 451892 KB Output is correct
3 Correct 1872 ms 325792 KB Output is correct
4 Correct 2012 ms 329596 KB Output is correct
5 Correct 1836 ms 325100 KB Output is correct
6 Correct 2953 ms 355172 KB Output is correct
7 Correct 2613 ms 351216 KB Output is correct
8 Correct 2819 ms 353500 KB Output is correct
9 Correct 2315 ms 348572 KB Output is correct
10 Correct 2402 ms 347532 KB Output is correct
11 Correct 2289 ms 347572 KB Output is correct
12 Correct 2355 ms 349512 KB Output is correct