oj.uz

Submission #667979

# Submission time Handle Problem Language Result Execution time Memory
667979 2022-12-02T13:10:37 Z Lobo Prize (CEOI22_prize) C++17
100 / 100
 3402 ms 403036 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 = 20;

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 l1 = lca1(u,v);
        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[l1] = dist1[u]-d1u;
        dist1[v] = dist1[l1]+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 1912 ms 238436 KB Output is correct
2 Correct 2003 ms 238768 KB Output is correct
3 Correct 1180 ms 192076 KB Output is correct
4 Correct 1124 ms 191960 KB Output is correct
5 Correct 1142 ms 192276 KB Output is correct
6 Correct 1529 ms 202152 KB Output is correct
7 Correct 1484 ms 202020 KB Output is correct
8 Correct 1380 ms 201928 KB Output is correct
9 Correct 1012 ms 192104 KB Output is correct
10 Correct 1022 ms 192260 KB Output is correct
11 Correct 1039 ms 191808 KB Output is correct
12 Correct 993 ms 192180 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1750 ms 238824 KB Output is correct
2 Correct 1701 ms 238276 KB Output is correct
3 Correct 1112 ms 192080 KB Output is correct
4 Correct 1111 ms 192384 KB Output is correct
5 Correct 1186 ms 192192 KB Output is correct
6 Correct 1507 ms 201868 KB Output is correct
7 Correct 1833 ms 202180 KB Output is correct
8 Correct 1831 ms 202204 KB Output is correct
9 Correct 1631 ms 200380 KB Output is correct
10 Correct 1518 ms 200284 KB Output is correct
11 Correct 1407 ms 199796 KB Output is correct
12 Correct 1486 ms 200220 KB Output is correct

Subtask #3
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 1195 ms 233864 KB Output is correct
2 Correct 1115 ms 233736 KB Output is correct
3 Correct 793 ms 187612 KB Output is correct
4 Correct 815 ms 187756 KB Output is correct
5 Correct 813 ms 187668 KB Output is correct
6 Correct 1083 ms 197592 KB Output is correct
7 Correct 988 ms 197660 KB Output is correct
8 Correct 1002 ms 197760 KB Output is correct
9 Correct 908 ms 195604 KB Output is correct
10 Correct 876 ms 195572 KB Output is correct
11 Correct 930 ms 195640 KB Output is correct
12 Correct 848 ms 195536 KB Output is correct

Subtask #4
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 2653 ms 398968 KB Output is correct
2 Correct 2729 ms 399036 KB Output is correct
3 Correct 1700 ms 306868 KB Output is correct
4 Correct 1697 ms 306656 KB Output is correct
5 Correct 1648 ms 306740 KB Output is correct
6 Correct 2492 ms 326604 KB Output is correct
7 Correct 2246 ms 326844 KB Output is correct
8 Correct 2346 ms 326628 KB Output is correct
9 Correct 2074 ms 322432 KB Output is correct
10 Correct 2122 ms 322616 KB Output is correct
11 Correct 1976 ms 322372 KB Output is correct
12 Correct 2082 ms 322392 KB Output is correct

Subtask #5
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 3402 ms 403036 KB Output is correct
2 Correct 3113 ms 402968 KB Output is correct
3 Correct 1873 ms 309800 KB Output is correct
4 Correct 1939 ms 310440 KB Output is correct
5 Correct 2447 ms 309732 KB Output is correct
6 Correct 2781 ms 330144 KB Output is correct
7 Correct 2684 ms 329560 KB Output is correct
8 Correct 2822 ms 329920 KB Output is correct
9 Correct 2423 ms 325640 KB Output is correct
10 Correct 2373 ms 325400 KB Output is correct
11 Correct 2428 ms 325548 KB Output is correct
12 Correct 2468 ms 325860 KB Output is correct