oj.uz

Submission #773257

# Submission time Handle Problem Language Result Execution time Memory
773257 2023-07-04T17:52:58 Z doowey Prize (CEOI22_prize) C++14
0 / 100
 607 ms 192292 KB 
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;

#define fi first
#define se second
#define mp make_pair
#define fastIO ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);

const int N = (int)1e6 + 10;
const int LOG = 20;
vector<int> nx[N];
vector<int> pik;
int par[N];

void dfs(int node){
    pik.push_back(node);
    for(auto x : nx[node]){
        par[x]=node;
        dfs(x);
    }
}

vector<pii> E[N];
int up[LOG][N];
int dep[N];
int tin[N];
int tout[N];
int tt;

void dfs1(int node, int pa){
    up[0][node]=pa;
    tt++;
    tin[node]=tt;
    for(int ln = 1; ln < LOG; ln ++ ){
        up[ln][node]=up[ln-1][up[ln-1][node]];
    }
    for(auto x : E[node]){
        dep[x.fi]=dep[node]+x.se;
        dfs1(x.fi, node);
    }
    tout[node]=tt;
}

bool is_anc(int u, int v){
    return tin[u] <= tin[v] && tout[u] >= tout[v];
}

int lca(int u, int v){
    if(is_anc(u,v)) return u;
    for(int ln = LOG - 1; ln >= 0 ; ln -- ){
        if(!is_anc(up[ln][u], v)) u = up[ln][u];
    }
    return up[0][u];
}

int main(){
    fastIO;
    int n, k, q, t;
    cin >> n >> k >> q >> t;
    int p;
    int root = -1;
    for(int i = 1; i <= n; i ++ ){
        cin >> p;
        if(p == -1){
            root = i;
        }
        else{
            nx[p].push_back(i);
        }
    }
    dfs(root);
    while(pik.size() > k) pik.pop_back();
    for(auto x : pik){
        cout << x << " ";
    }
    cout << "\n";
    fflush(stdout);
    for(int i = 1; i < pik.size(); i ++ ){
        cout << "? " << par[i] << " " << i << "\n";
    }
    cout << "!\n";
    fflush(stdout);
    int a, b, c, d;
    for(int i = 1; i < pik.size(); i ++ ){
        cin >> a >> b >> c >> d;
        E[par[pik[i]]].push_back(mp(pik[i],b));
    }
    dfs1(root, root);
    int u, v;
    int sol;
    vector<pii> qq;
    for(int it = 1; it <= t; it ++ ){
        cin >> u >> v;
        qq.push_back(mp(u,v));
        sol = dep[u] + dep[v] - 2 * dep[lca(u,v)];
        //cout << sol << " " << sol << "\n";
    }
    for(auto x : qq){
        sol = dep[x.fi] + dep[x.se] - 2 * dep[lca(x.fi,x.se)];
        cout << sol << " " << sol << "\n";
    }
    fflush(stdout);
    return 0;
}

Compilation message

Main.cpp: In function 'int main()':
Main.cpp:76:22: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   76 |     while(pik.size() > k) pik.pop_back();
      |           ~~~~~~~~~~~^~~
Main.cpp:82:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   82 |     for(int i = 1; i < pik.size(); i ++ ){
      |                    ~~^~~~~~~~~~~~
Main.cpp:88:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   88 |     for(int i = 1; i < pik.size(); i ++ ){
      |                    ~~^~~~~~~~~~~~

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 262 ms 90508 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 270 ms 90476 KB Time limit exceeded (wall clock)
2 Halted 0 ms 0 KB -

Subtask #3
0 / 19.0

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

Subtask #4
0 / 22.0

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

Subtask #5
0 / 24.0

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