oj.uz

Submission #667980

# Submission time Handle Problem Language Result Execution time Memory
667980 2022-12-02T13:11:32 Z Lobo Prize (CEOI22_prize) C++17
100 / 100
 3289 ms 395344 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 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 1695 ms 234464 KB Output is correct
2 Correct 1725 ms 234856 KB Output is correct
3 Correct 1037 ms 188196 KB Output is correct
4 Correct 996 ms 188132 KB Output is correct
5 Correct 1044 ms 188544 KB Output is correct
6 Correct 1421 ms 198192 KB Output is correct
7 Correct 1389 ms 198152 KB Output is correct
8 Correct 1375 ms 198176 KB Output is correct
9 Correct 1016 ms 188096 KB Output is correct
10 Correct 1250 ms 188312 KB Output is correct
11 Correct 964 ms 187824 KB Output is correct
12 Correct 978 ms 188272 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1702 ms 234904 KB Output is correct
2 Correct 1638 ms 234276 KB Output is correct
3 Correct 1135 ms 188180 KB Output is correct
4 Correct 1093 ms 188444 KB Output is correct
5 Correct 1020 ms 188284 KB Output is correct
6 Correct 1453 ms 197784 KB Output is correct
7 Correct 1808 ms 198244 KB Output is correct
8 Correct 1665 ms 198224 KB Output is correct
9 Correct 1322 ms 196340 KB Output is correct
10 Correct 1410 ms 196436 KB Output is correct
11 Correct 1617 ms 195824 KB Output is correct
12 Correct 1297 ms 196528 KB Output is correct

Subtask #3
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 1065 ms 229860 KB Output is correct
2 Correct 1133 ms 229900 KB Output is correct
3 Correct 799 ms 183768 KB Output is correct
4 Correct 756 ms 183780 KB Output is correct
5 Correct 767 ms 183768 KB Output is correct
6 Correct 1002 ms 193792 KB Output is correct
7 Correct 937 ms 193696 KB Output is correct
8 Correct 1071 ms 193788 KB Output is correct
9 Correct 1041 ms 191704 KB Output is correct
10 Correct 841 ms 191596 KB Output is correct
11 Correct 1004 ms 191528 KB Output is correct
12 Correct 822 ms 191592 KB Output is correct

Subtask #4
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 2631 ms 391004 KB Output is correct
2 Correct 2445 ms 391200 KB Output is correct
3 Correct 1615 ms 298936 KB Output is correct
4 Correct 1967 ms 298796 KB Output is correct
5 Correct 1593 ms 298860 KB Output is correct
6 Correct 2569 ms 318908 KB Output is correct
7 Correct 2235 ms 319060 KB Output is correct
8 Correct 2048 ms 318932 KB Output is correct
9 Correct 2003 ms 314664 KB Output is correct
10 Correct 1970 ms 314676 KB Output is correct
11 Correct 2001 ms 314524 KB Output is correct
12 Correct 1968 ms 314708 KB Output is correct

Subtask #5
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 3289 ms 395344 KB Output is correct
2 Correct 3116 ms 395200 KB Output is correct
3 Correct 1814 ms 302008 KB Output is correct
4 Correct 1845 ms 302532 KB Output is correct
5 Correct 1711 ms 301976 KB Output is correct
6 Correct 2624 ms 322360 KB Output is correct
7 Correct 2544 ms 321720 KB Output is correct
8 Correct 2656 ms 322220 KB Output is correct
9 Correct 2201 ms 317840 KB Output is correct
10 Correct 2147 ms 317700 KB Output is correct
11 Correct 2153 ms 317808 KB Output is correct
12 Correct 2258 ms 318104 KB Output is correct