Submission #1147350

#	Time	Username	Problem	Language	Result	Execution time	Memory
1147350		thunopro	Prize (CEOI22_prize)	C++20	100 / 100	2050 ms	584996 KiB

Main

#include<bits/stdc++.h>
#define f first
#define s second
#define int long long
#define pii pair<int,int>
using namespace std;
const int N = 1e6 + 5, mod = 1e9 + 7; // !
int t, tmin[2][N], tmout[2][N], p[2][N][22],  timer= 0, k;
pii q[N][2];
int h[2][N], ans[N][2];
vector<int> x,V[2][N];
bool check(int u, int v, int t) {
    return (tmin[t][u] <= tmin[t][v] && tmin[t][v] <= tmout[t][u]);
}
int lca(int u,int v, int t) {
    if(check(u, v, t)) return u;
    if(check(v, u, t))return v;

    for(int i = 20; i >= 0; i--) {
        if(p[t][u][i] && !check(p[t][u][i], v, t))  u = p[t][u][i];
    }
    return p[t][u][0];
}
void dfs(int u, int t) {
    tmin[t][u] = ++timer;
    if(x.size() < k) x.push_back(u);
    for(int i = 1; i <= 20; i++) p[t][u][i] = p[t][p[t][u][i - 1]][i - 1];
    for(int i = 0; i < V[t][u].size(); i++) p[t][V[t][u][i]][0] = u, dfs(V[t][u][i], t); 
    tmout[t][u] = timer;
}
bool cmp(int x,int y) {
    return (tmin[1][x] < tmin[1][y]);
}
main(){
    int n,  Q, T;
    cin >> n >> k >> Q >> T;
    vector<int> r(2);
    for(int t = 0; t < 2; ++t) {

        for(int i = 1; i <= n; i++) {
            int p;
            cin >> p;
            if(p == -1) r[t] = i;
            else V[t][p].push_back(i);
        }
    }
    dfs(r[0], 0);
    timer = 0;
    dfs(r[1], 1);
    sort(x.begin(), x.end(), cmp);
    
    for(int i = 0; i < x.size(); i++) cout << x[i] << " ";
    cout << endl;
    for(int i = 1; i < x.size(); i++) {
        cout << "? " << x[i - 1] << " " << x[i] << endl;
    }
    cout << "!" << endl; 
    h[0][x[0]] = h[1][x[0]] = 0;
    for(int i = 1; i < x.size(); i++) {
        for(int t = 0; t < 2; t++) {
            cin >> q[i][t].f >> q[i][t].s;
            h[t][lca(x[i - 1], x[i], t)] = h[t][x[i - 1]] - q[i][t].f;
            h[t][x[i]] = h[t][x[i - 1]] - q[i][t].f + q[i][t].s;
        }
    }
    
	
    for(int i = 1; i <= T; i++) {
        int u, v;
        cin >> u >> v;
        for(int t = 0; t < 2; t++) ans[i][t] = h[t][u] + h[t][v] - 2 * h[t][lca(u, v, t)];
    }
    for(int i = 1; i <= T; i++) cout << ans[i][0] << " " << ans[i][1] << endl;

 }

Compilation message (stderr)

Main.cpp:34:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   34 | main(){
      | ^~~~

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