oj.uz

Submission #773261

# Submission time Handle Problem Language Result Execution time Memory
773261 2023-07-04T17:56:43 Z doowey Prize (CEOI22_prize) C++14
10 / 100
 1172 ms 228040 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;
    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[pik[i]] << " " << pik[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:77:22: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   77 |     while(pik.size() > k) pik.pop_back();
      |           ~~~~~~~~~~~^~~
Main.cpp:83:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   83 |     for(int i = 1; i < pik.size(); i ++ ){
      |                    ~~^~~~~~~~~~~~
Main.cpp:89:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   89 |     for(int i = 1; i < pik.size(); i ++ ){
      |                    ~~^~~~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 847 ms 139412 KB Output is correct
2 Correct 848 ms 140212 KB Output is correct
3 Correct 777 ms 107580 KB Output is correct
4 Correct 750 ms 107472 KB Output is correct
5 Correct 745 ms 107932 KB Output is correct
6 Correct 894 ms 114504 KB Output is correct
7 Correct 814 ms 114516 KB Output is correct
8 Correct 799 ms 114336 KB Output is correct
9 Correct 703 ms 107568 KB Output is correct
10 Correct 788 ms 107828 KB Output is correct
11 Correct 722 ms 107296 KB Output is correct
12 Correct 762 ms 107776 KB Output is correct

Subtask #2
0 / 25.0

# Verdict Execution time Memory Grader output
1 Runtime error 606 ms 140112 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 425 ms 106484 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 945 ms 193048 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 1172 ms 228040 KB Execution killed with signal 13
2 Halted 0 ms 0 KB -