oj.uz

Submission #796421

# Submission time Handle Problem Language Result Execution time Memory
796421 2023-07-28T11:27:46 Z practice Prize (CEOI22_prize) C++14
10 / 100
 3165 ms 451024 KB 
//BITARO BITARO BITARO
// testing
#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;
            if(t == 0){
				adj[t][u].push_back({l, -c1});
				adj[t][v].push_back({l, -c2});
			}
            adj[t][l].push_back({u, c1});
            adj[t][l].push_back({v, 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:61:24: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   61 |     while(nodes.size() > k) nodes.pop_back();
      |           ~~~~~~~~~~~~~^~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1494 ms 274392 KB Output is correct
2 Correct 1568 ms 276612 KB Output is correct
3 Correct 984 ms 212596 KB Output is correct
4 Correct 925 ms 212192 KB Output is correct
5 Correct 1018 ms 214016 KB Output is correct
6 Correct 1271 ms 226224 KB Output is correct
7 Correct 1412 ms 226040 KB Output is correct
8 Correct 1398 ms 225504 KB Output is correct
9 Correct 978 ms 212412 KB Output is correct
10 Correct 946 ms 213780 KB Output is correct
11 Correct 945 ms 211408 KB Output is correct
12 Correct 995 ms 213304 KB Output is correct

Subtask #2
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1798 ms 276700 KB Output is correct
2 Correct 1624 ms 273596 KB Output is correct
3 Runtime error 849 ms 209484 KB Execution killed with signal 13
4 Halted 0 ms 0 KB -

Subtask #3
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 1075 ms 263696 KB Output is correct
2 Correct 1190 ms 263712 KB Output is correct
3 Runtime error 672 ms 200448 KB Execution killed with signal 13
4 Halted 0 ms 0 KB -

Subtask #4
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 2580 ms 437860 KB Output is correct
2 Correct 2645 ms 437916 KB Output is correct
3 Runtime error 1453 ms 308844 KB Execution killed with signal 13
4 Halted 0 ms 0 KB -

Subtask #5
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 3164 ms 451024 KB Output is correct
2 Correct 3165 ms 450632 KB Output is correct
3 Runtime error 1540 ms 316348 KB Execution killed with signal 13
4 Halted 0 ms 0 KB -