oj.uz

Submission #1106215

# Submission time Handle Problem Language Result Execution time Memory
1106215 2024-10-29T14:25:41 Z PagodePaiva Prize (CEOI22_prize) C++17
0 / 100
 690 ms 144364 KB 
#include<bits/stdc++.h>

using namespace std;

const int N = 500010;
const int LOGN = 20;

vector <int> g[N];
int st;
int ans[N];

struct Binary_lifting{
    int pai[N][LOGN], val[N][LOGN], h[N];
    void dfs(int v, int p){
        pai[v][0] = p;
        val[v][0] = ans[v];
        for(auto x : g[v]){
            if(x == p) continue;
            h[x] = h[v]+1;
            dfs(x, v);
        }
        return;
    }
    void build(int n){
        h[st] = 0;
        dfs(st, st);
        for(int bit = 1;bit < LOGN;bit++){
            for(int i = 1;i <= n;i++){
                pai[i][bit] = pai[pai[i][bit-1]][bit-1];
                val[i][bit] = val[i][bit-1] + val[pai[i][bit-1]][bit-1];
            }
        }
        return;
    }
    int query(int a, int b){
        if(h[a] > h[b]) swap(a, b);
        int t = h[b]-h[a];
        int res = 0;
        for(int bit=0;bit < LOGN;bit++){
            if((1<<bit)&t){
                res += val[b][bit];
                b = pai[b][bit];
            }
        }
        if(a == b) return res;
        for(int bit = LOGN-1;bit >= 0;bit--){
            if(pai[a][bit] != pai[b][bit]){
                res += val[a][bit];
                res += val[b][bit];
                a = pai[a][bit];
                b = pai[b][bit];
            }
        }
        return res+val[a][0]+val[b][0];
    }
} bin;

int n, k,q , t;
int pai[N];

vector <int> vertices;

void dfs2(int v, int p){
    if(v != p){
        if(vertices.size() < k){
            cout << "? " << v << ' ' << p << '\n';
        }
    }
    if(vertices.size() < k) vertices.push_back(v);
    for(auto x : g[v]){
        if(x == p) continue;
        dfs2(x, v);
    }
    return;
}

void dfs(int v, int p){
    if(vertices.size()< k) vertices.push_back(v);
    for(auto x : g[v]){
        if(x == p) continue;
        dfs(x, v);
    }
    return;
}

int32_t main(){
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    cin >> n >> k >> q >> t;
    for(int i = 1;i <= n;i++){
        cin >> pai[i];
        if(pai[i] == -1)st = i;
    }
    for(int i = 1;i <= n;i++){
        cin >> pai[i];
        if(pai[i] == -1) continue;
        g[i].push_back(pai[i]);
        g[pai[i]].push_back(i);
    }
    dfs(st, st);
    for(auto x : vertices){
        cout << x << ' ';
    }
    cout.flush();
    cout << '\n';
    vertices.clear();
    dfs2(st, st);
    cout << "!\n";
    cout.flush();
    for(auto v : vertices){
        int cu;
        if(pai[v] == -1) continue;
        cin >> ans[v];
        cin >> cu;
        cin >> cu;
        cin >> cu;
    }
    bin.build(n);
    vector <pair <int, int>> queries;
    while(q--){
        int a, b;
        cin >> a >> b;
        queries.push_back({a,b});
    }
    for(auto [a, b] : queries){
        cout << bin.query(a,b) << ' ' << bin.query(a, b) << '\n';
    }
    cout.flush();
    return 0;
}

Compilation message

Main.cpp: In function 'void dfs2(int, int)':
Main.cpp:65:28: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   65 |         if(vertices.size() < k){
      |            ~~~~~~~~~~~~~~~~^~~
Main.cpp:69:24: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   69 |     if(vertices.size() < k) vertices.push_back(v);
      |        ~~~~~~~~~~~~~~~~^~~
Main.cpp: In function 'void dfs(int, int)':
Main.cpp:78:23: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   78 |     if(vertices.size()< k) vertices.push_back(v);
      |        ~~~~~~~~~~~~~~~^~~

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 690 ms 144364 KB Time limit exceeded (wall clock)
2 Halted 0 ms 0 KB -

Subtask #2
0 / 25.0

# Verdict Execution time Memory Grader output
1 Execution timed out 531 ms 141484 KB Time limit exceeded (wall clock)
2 Halted 0 ms 0 KB -

Subtask #3
0 / 19.0

# Verdict Execution time Memory Grader output
1 Incorrect 583 ms 138572 KB Wrong answer
2 Halted 0 ms 0 KB -

Subtask #4
0 / 22.0

# Verdict Execution time Memory Grader output
1 Runtime error 52 ms 32512 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #5
0 / 24.0

# Verdict Execution time Memory Grader output
1 Runtime error 52 ms 32512 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -