Submission #1106291

#	Time	Username	Problem	Language	Result	Execution time	Memory
1106291		Lobo	Prize (CEOI22_prize)	C++17	0 / 100	428 ms	101228 KiB

Main

#include<bits/stdc++.h>
#define int long long
 
using namespace std;
 
const int N = 500010;
const int K = 100010;
const int LOGN = 20;
 
int n, k,q , t;
vector <int> g[N];
int st;
int ans[N];
int mp[N];
set <int> vvv;
 
struct Binary_lifting{
    int pai[K][LOGN], val[K][LOGN], h[K];
    void dfs(int v, int p){
        pai[v][0] = p;
        val[v][0] = ans[v];
        for(auto x : g[v]){
            if(vvv.find(x) == vvv.end()) continue;
            x = mp[x];
            if(x == p) continue;
            h[x] = h[v]+1;
            dfs(x, v);
        }
        return;
    }
    void build(int n){
        h[mp[st]] = 0;
        dfs(mp[st], mp[st]);
        for(int bit = 1;bit < LOGN;bit++){
            for(int i = 1;i <= k;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){
        a = mp[a];
        b = mp[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 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();
    int con = 1;
    for(auto v : vertices){
        int cu;
        mp[v] = con;
        con++;
        if(pai[v] == -1) continue;
        cin >> ans[v];
        cin >> cu;
        cin >> cu;
        cin >> cu;
    }
    bin.build(n);
    vector <pair <int, int>> queries;
    while(t--){
        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 (stderr)

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

• Subtask 1: 0 / 10
• Subtask 2: 0 / 25
• Subtask 3: 0 / 19
• Subtask 4: 0 / 22
• Subtask 5: 0 / 24