oj.uz

Submission #796410

# Submission time Handle Problem Language Result Execution time Memory
796410 2023-07-28T11:17:56 Z practice Prize (CEOI22_prize) C++14
100 / 100
 3395 ms 452528 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]++;
    //cout << time_in[t][u] << " " << t << " " << u << '\n';
    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;
        //cout << v << " " << w << " DEBUG\n";
        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:60:24: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   60 |     while(nodes.size() > k) nodes.pop_back();
      |           ~~~~~~~~~~~~~^~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1689 ms 275560 KB Output is correct
2 Correct 1798 ms 278100 KB Output is correct
3 Correct 1012 ms 214332 KB Output is correct
4 Correct 987 ms 213976 KB Output is correct
5 Correct 1031 ms 216264 KB Output is correct
6 Correct 1396 ms 228032 KB Output is correct
7 Correct 1394 ms 227908 KB Output is correct
8 Correct 1461 ms 227228 KB Output is correct
9 Correct 992 ms 214296 KB Output is correct
10 Correct 1028 ms 215716 KB Output is correct
11 Correct 997 ms 212804 KB Output is correct
12 Correct 1066 ms 215448 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 2054 ms 278088 KB Output is correct
2 Correct 1821 ms 274320 KB Output is correct
3 Correct 1092 ms 214272 KB Output is correct
4 Correct 1160 ms 216512 KB Output is correct
5 Correct 1175 ms 215016 KB Output is correct
6 Correct 1586 ms 226040 KB Output is correct
7 Correct 1522 ms 228984 KB Output is correct
8 Correct 1598 ms 229148 KB Output is correct
9 Correct 1318 ms 227116 KB Output is correct
10 Correct 1465 ms 227960 KB Output is correct
11 Correct 1353 ms 224436 KB Output is correct
12 Correct 1557 ms 227720 KB Output is correct

Subtask #3
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 1165 ms 263720 KB Output is correct
2 Correct 1091 ms 263724 KB Output is correct
3 Correct 791 ms 202184 KB Output is correct
4 Correct 747 ms 202284 KB Output is correct
5 Correct 778 ms 202240 KB Output is correct
6 Correct 914 ms 215164 KB Output is correct
7 Correct 923 ms 215092 KB Output is correct
8 Correct 923 ms 215180 KB Output is correct
9 Correct 860 ms 213104 KB Output is correct
10 Correct 803 ms 212920 KB Output is correct
11 Correct 848 ms 212916 KB Output is correct
12 Correct 866 ms 212912 KB Output is correct

Subtask #4
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 2789 ms 437860 KB Output is correct
2 Correct 2698 ms 437968 KB Output is correct
3 Correct 1800 ms 315440 KB Output is correct
4 Correct 1837 ms 315100 KB Output is correct
5 Correct 1755 ms 315104 KB Output is correct
6 Correct 2191 ms 340820 KB Output is correct
7 Correct 2308 ms 341272 KB Output is correct
8 Correct 2282 ms 340832 KB Output is correct
9 Correct 2001 ms 336844 KB Output is correct
10 Correct 1965 ms 336744 KB Output is correct
11 Correct 2063 ms 336532 KB Output is correct
12 Correct 1990 ms 336756 KB Output is correct

Subtask #5
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 3395 ms 452528 KB Output is correct
2 Correct 3244 ms 451984 KB Output is correct
3 Correct 1928 ms 325756 KB Output is correct
4 Correct 2027 ms 329428 KB Output is correct
5 Correct 1884 ms 325136 KB Output is correct
6 Correct 3147 ms 355028 KB Output is correct
7 Correct 2826 ms 351084 KB Output is correct
8 Correct 2947 ms 353556 KB Output is correct
9 Correct 2508 ms 348412 KB Output is correct
10 Correct 2378 ms 347480 KB Output is correct
11 Correct 2402 ms 347452 KB Output is correct
12 Correct 2452 ms 349412 KB Output is correct