oj.uz

Submission #667981

# Submission time Handle Problem Language Result Execution time Memory
667981 2022-12-02T13:16:45 Z Lobo Prize (CEOI22_prize) C++17
100 / 100
 2660 ms 395372 KB 
#include<bits/stdc++.h>
using namespace std;
const long long inf = (long long) 1e18 + 10;
const int inf1 = (int) 1e9 + 10;
// #define int long long
#define dbl long double
#define endl '\n'
#define sc second
#define fr first
#define mp make_pair
#define pb push_back
#define all(x) x.begin(), x.end()

const int maxn = 1e6+10;
const int LOG = 19;

int n, k, q, t;
int pp1[maxn][LOG+1], pp2[maxn][LOG+1], tin1[maxn], tin2[maxn], withtin1[maxn], withtin2[maxn], h1[maxn], h2[maxn];
int timer1, timer2, dist1[maxn], dist2[maxn], r1, r2, p1[maxn], p2[maxn];
vector<int> g1[maxn], g2[maxn];
vector<pair<int,pair<int,int>>> g1d[maxn];
void dfstin1(int u) {
    for(int i = 1; i <= LOG; i++) {
        pp1[u][i] = pp1[pp1[u][i-1]][i-1];
    }
    tin1[u] = ++timer1;
    withtin1[tin1[u]] = u;
    for(auto v : g1[u]) {
        pp1[v][0] = u;
        h1[v] = h1[u]+1;
        dfstin1(v);
    }
}

int lca1(int u, int v) {
    if(h1[u] < h1[v]) swap(u,v);

    for(int i = LOG; i >= 0; i--) {
        if(h1[pp1[u][i]] >= h1[v]) {
            u = pp1[u][i];
        }
    }
    if(u == v) return u;

    for(int i = LOG; i >= 0; i--) {
        if(pp1[u][i] != pp1[v][i]) {
            u = pp1[u][i];
            v = pp1[v][i];
        }
    }
    return pp1[u][0];
}

void dfstin2(int u) {
    for(int i = 1; i <= LOG; i++) {
        pp2[u][i] = pp2[pp2[u][i-1]][i-1];
    }
    tin2[u] = ++timer2;
    withtin2[tin2[u]] = u;
    for(auto v : g2[u]) {
        h2[v] = h2[u]+1;
        pp2[v][0] = u;
        dfstin2(v);
    }
}

int lca2(int u, int v) {
    if(h2[u] < h2[v]) swap(u,v);

    for(int i = LOG; i >= 0; i--) {
        if(h2[pp2[u][i]] >= h2[v]) {
            u = pp2[u][i];
        }
    }
    if(u == v) return u;

    for(int i = LOG; i >= 0; i--) {
        if(pp2[u][i] != pp2[v][i]) {
            u = pp2[u][i];
            v = pp2[v][i];
        }
    }
    return pp2[u][0];
}

void solve() {
    cin >> n >> k >> q >> t;
    for(int i = 1; i <= n; i++) {
        cin >> p1[i];
        if(p1[i] == -1) {
            r1 = i;
        }
        else {
            g1[p1[i]].pb(i);
        }
    }

    for(int i = 1; i <= n; i++) {
        cin >> p2[i];
        if(p2[i] == -1) {
            r2 = i;
        }
        else {
            g2[p2[i]].pb(i);
        }
    }

    pp1[r1][0] = r1; dfstin1(r1);
    pp2[r2][0] = r2; dfstin2(r2);

    vector<pair<int,int>> vrt;
    for(int i = 1; i <= k; i++) {
        vrt.pb(mp(tin2[withtin1[i]],withtin1[i]));
    }

    if(tin1[r2] > k) {
        vrt.pop_back();
        vrt.pb(mp(tin2[r2],r2));
    }

    sort(all(vrt));
    for(auto x : vrt) {
        cout << x.sc << " ";
    }cout << endl;
    cout.flush();

    vector<pair<int,int>> asks;

    for(int i = 0; i+1 < vrt.size(); i++) {
        int u = vrt[i].sc;
        int v = vrt[i+1].sc;
        cout << "? " << u << " " << v << endl;
        asks.pb(mp(u,v));        
    }
    cout << "!" << endl;
    cout.flush();
    dist1[r2] = 0;
    dist2[r2] = 0;

    for(int i = 0; i < asks.size(); i++) {
        int u = asks[i].fr;
        int v = asks[i].sc;
        int l2 = lca2(u,v);
        int d1u, d1v, d2u, d2v;
        cin >> d1u >> d1v >> d2u >> d2v;

        dist2[l2] = dist2[u]-d2u;
        dist2[v] = dist2[l2]+d2v;
        dist1[v] = dist1[u]-d1u+d1v;
    }

    vector<pair<long long,long long>> ans;
    for(int i = 1; i <= t; i++) {
        int u,v; cin >> u >> v;
        ans.pb(mp((long long) dist1[u]+dist1[v]-2*dist1[lca1(u,v)],(long long) dist2[u]+dist2[v]-2*dist2[lca2(u,v)]));
    }

    for(int i = 1; i <= t; i++) {
        cout << ans[i-1].fr << " " << ans[i-1].sc << endl;
    }
    cout.flush();
}

int32_t main() {
    ios::sync_with_stdio(false); cin.tie(0);

    // freopen("in.in", "r", stdin);
    // freopen("out.out", "w", stdout);
    int tt = 1;
    // cin >> tt;
    while(tt--) {
        solve();
    }
    return 0;

}

Compilation message

Main.cpp: In function 'void solve()':
Main.cpp:129:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  129 |     for(int i = 0; i+1 < vrt.size(); i++) {
      |                    ~~~~^~~~~~~~~~~~
Main.cpp:140:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  140 |     for(int i = 0; i < asks.size(); i++) {
      |                    ~~^~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1294 ms 234568 KB Output is correct
2 Correct 1346 ms 235068 KB Output is correct
3 Correct 900 ms 188200 KB Output is correct
4 Correct 903 ms 188028 KB Output is correct
5 Correct 888 ms 188556 KB Output is correct
6 Correct 1254 ms 198396 KB Output is correct
7 Correct 1213 ms 198116 KB Output is correct
8 Correct 1238 ms 198064 KB Output is correct
9 Correct 904 ms 188384 KB Output is correct
10 Correct 878 ms 188476 KB Output is correct
11 Correct 923 ms 188012 KB Output is correct
12 Correct 862 ms 188436 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1445 ms 234952 KB Output is correct
2 Correct 1357 ms 234336 KB Output is correct
3 Correct 922 ms 188272 KB Output is correct
4 Correct 956 ms 188584 KB Output is correct
5 Correct 984 ms 188276 KB Output is correct
6 Correct 1338 ms 197832 KB Output is correct
7 Correct 1298 ms 198312 KB Output is correct
8 Correct 1358 ms 198320 KB Output is correct
9 Correct 1128 ms 196284 KB Output is correct
10 Correct 1179 ms 196556 KB Output is correct
11 Correct 1096 ms 195936 KB Output is correct
12 Correct 1122 ms 196400 KB Output is correct

Subtask #3
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 1047 ms 229896 KB Output is correct
2 Correct 1016 ms 229960 KB Output is correct
3 Correct 692 ms 183940 KB Output is correct
4 Correct 734 ms 183768 KB Output is correct
5 Correct 676 ms 183752 KB Output is correct
6 Correct 860 ms 193704 KB Output is correct
7 Correct 836 ms 193736 KB Output is correct
8 Correct 858 ms 193776 KB Output is correct
9 Correct 791 ms 191576 KB Output is correct
10 Correct 792 ms 191532 KB Output is correct
11 Correct 796 ms 191592 KB Output is correct
12 Correct 798 ms 191636 KB Output is correct

Subtask #4
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 2268 ms 390956 KB Output is correct
2 Correct 2311 ms 391160 KB Output is correct
3 Correct 1529 ms 299080 KB Output is correct
4 Correct 1511 ms 298792 KB Output is correct
5 Correct 1488 ms 298944 KB Output is correct
6 Correct 2107 ms 318836 KB Output is correct
7 Correct 1991 ms 319024 KB Output is correct
8 Correct 1973 ms 318724 KB Output is correct
9 Correct 1800 ms 314744 KB Output is correct
10 Correct 1785 ms 314668 KB Output is correct
11 Correct 1842 ms 314524 KB Output is correct
12 Correct 1950 ms 314544 KB Output is correct

Subtask #5
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 2652 ms 395372 KB Output is correct
2 Correct 2660 ms 395224 KB Output is correct
3 Correct 1702 ms 302264 KB Output is correct
4 Correct 1801 ms 302680 KB Output is correct
5 Correct 1722 ms 301872 KB Output is correct
6 Correct 2546 ms 322312 KB Output is correct
7 Correct 2368 ms 321708 KB Output is correct
8 Correct 2463 ms 322084 KB Output is correct
9 Correct 2118 ms 317900 KB Output is correct
10 Correct 2001 ms 317672 KB Output is correct
11 Correct 2041 ms 317968 KB Output is correct
12 Correct 2063 ms 318004 KB Output is correct