oj.uz

Submission #796407

# Submission time Handle Problem Language Result Execution time Memory
796407 2023-07-28T11:16:40 Z practice Prize (CEOI22_prize) C++14
10 / 100
 2982 ms 440872 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 1628 ms 273376 KB Output is correct
2 Correct 1665 ms 275108 KB Output is correct
3 Correct 1004 ms 210884 KB Output is correct
4 Correct 985 ms 210540 KB Output is correct
5 Correct 976 ms 211772 KB Output is correct
6 Correct 1286 ms 224412 KB Output is correct
7 Correct 1288 ms 224252 KB Output is correct
8 Correct 1353 ms 223992 KB Output is correct
9 Correct 1008 ms 210732 KB Output is correct
10 Correct 946 ms 211600 KB Output is correct
11 Correct 923 ms 210184 KB Output is correct
12 Correct 956 ms 211268 KB Output is correct

Subtask #2
0 / 25.0

# Verdict Execution time Memory Grader output
1 Runtime error 1437 ms 270552 KB Execution killed with signal 13
2 Halted 0 ms 0 KB -

Subtask #3
0 / 19.0

# Verdict Execution time Memory Grader output
1 Runtime error 1008 ms 262312 KB Execution killed with signal 13
2 Halted 0 ms 0 KB -

Subtask #4
0 / 22.0

# Verdict Execution time Memory Grader output
1 Runtime error 2390 ms 432844 KB Execution killed with signal 13
2 Halted 0 ms 0 KB -

Subtask #5
0 / 24.0

# Verdict Execution time Memory Grader output
1 Runtime error 2982 ms 440872 KB Execution killed with signal 13
2 Halted 0 ms 0 KB -