oj.uz

Submission #667974

# Submission time Handle Problem Language Result Execution time Memory
667974 2022-12-02T13:01:14 Z Lobo Prize (CEOI22_prize) C++17
100 / 100
 3384 ms 406028 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 dfsd1(int u, int ant) {
    assert(g1d[u].size() == 1 || g1d[u].size() == 2);
    int v = -1;
    int d1u, d1v;
    for(auto V : g1d[u]) if(V.fr != ant) {
        v = V.fr;
        d1u = V.sc.fr;
        d1v = V.sc.sc;
        int l1 = lca1(u,v);
        dist1[l1] = dist1[u]-d1u;
        dist1[v] = dist1[l1]+d1v;
        dfsd1(v,u);
    }
    // if(v == -1) return;

    // int l1 = lca1(u,v);
    // dist1[l1] = dist1[u]-d1u;
    // dist1[v] = dist1[l1]+d1v;
    // dfsd1(v,u);
}


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

    for(int i = 1; i <= n; i++) {
        // int wtf; cin >> wtf;
        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;
    // for(int i = 1; i <= k; i++) {
    //     cout << i << " ";
    // }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));        
    }
    // for(int i = 1; i <= k-1; i++) {
    //     cout << "? " << i << " " << i+1 << endl;
    // }
    cout << "!" << endl;
    cout.flush();
    // for(int i = 1; i <= k-1; i++) {
    //     int x; cin >> x >> x >> x >> x;
    // }

    for(int i = 1; i <= n; i++) dist1[i] = -1;
    for(int i = 1; i <= n; i++) dist2[i] = -1;
    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;

        g1d[u].pb(mp(v,mp(d1u,d1v)));
        g1d[v].pb(mp(u,mp(d1v,d1u)));
    }

    dist1[r1] = 0;
    dfsd1(r1,-1);

    vector<pair<long long,long long>> ans;
    for(int i = 1; i <= t; i++) {
        int u,v; cin >> u >> v;
        // assert(dist1[lca1(u,v)] != -1);
        assert(dist1[u] != -1);
        assert(dist1[v] != -1);
        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++) {
        // int u,v; cin >> u >> v;
        // cout << dist1[u]+dist1[v]-2*dist1[lca1(u,v)] << " " << dist2[u]+dist2[v]-2*dist2[lca2(u,v)] << endl;
        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:156: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]
  156 |     for(int i = 0; i+1 < vrt.size(); i++) {
      |                    ~~~~^~~~~~~~~~~~
Main.cpp:175: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]
  175 |     for(int i = 0; i < asks.size(); i++) {
      |                    ~~^~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1754 ms 240516 KB Output is correct
2 Correct 1829 ms 241584 KB Output is correct
3 Correct 1231 ms 199516 KB Output is correct
4 Correct 1257 ms 199016 KB Output is correct
5 Correct 1301 ms 202024 KB Output is correct
6 Correct 1694 ms 204880 KB Output is correct
7 Correct 2008 ms 204820 KB Output is correct
8 Correct 1795 ms 204200 KB Output is correct
9 Correct 1235 ms 199332 KB Output is correct
10 Correct 1308 ms 201340 KB Output is correct
11 Correct 1232 ms 197668 KB Output is correct
12 Correct 1264 ms 200788 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1990 ms 241576 KB Output is correct
2 Correct 1882 ms 239744 KB Output is correct
3 Correct 1360 ms 198436 KB Output is correct
4 Correct 1370 ms 199632 KB Output is correct
5 Correct 1310 ms 198540 KB Output is correct
6 Correct 1679 ms 203440 KB Output is correct
7 Correct 1798 ms 204968 KB Output is correct
8 Correct 1872 ms 205144 KB Output is correct
9 Correct 1566 ms 202944 KB Output is correct
10 Correct 1503 ms 203416 KB Output is correct
11 Correct 1460 ms 201824 KB Output is correct
12 Correct 1557 ms 203792 KB Output is correct

Subtask #3
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 1257 ms 236280 KB Output is correct
2 Correct 1420 ms 236412 KB Output is correct
3 Correct 891 ms 190004 KB Output is correct
4 Correct 903 ms 189876 KB Output is correct
5 Correct 937 ms 189896 KB Output is correct
6 Correct 1128 ms 200072 KB Output is correct
7 Correct 1159 ms 199932 KB Output is correct
8 Correct 1098 ms 200000 KB Output is correct
9 Correct 1048 ms 197696 KB Output is correct
10 Correct 993 ms 197712 KB Output is correct
11 Correct 1022 ms 197860 KB Output is correct
12 Correct 1074 ms 197756 KB Output is correct

Subtask #4
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 2826 ms 401688 KB Output is correct
2 Correct 2851 ms 401800 KB Output is correct
3 Correct 1982 ms 308996 KB Output is correct
4 Correct 2017 ms 308940 KB Output is correct
5 Correct 2103 ms 308884 KB Output is correct
6 Correct 2611 ms 328824 KB Output is correct
7 Correct 2503 ms 328744 KB Output is correct
8 Correct 2529 ms 328632 KB Output is correct
9 Correct 2329 ms 324532 KB Output is correct
10 Correct 2299 ms 324548 KB Output is correct
11 Correct 2272 ms 324460 KB Output is correct
12 Correct 2349 ms 324828 KB Output is correct

Subtask #5
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 3367 ms 406028 KB Output is correct
2 Correct 3384 ms 405832 KB Output is correct
3 Correct 2217 ms 315932 KB Output is correct
4 Correct 2322 ms 317744 KB Output is correct
5 Correct 2166 ms 315524 KB Output is correct
6 Correct 3006 ms 333072 KB Output is correct
7 Correct 2862 ms 331272 KB Output is correct
8 Correct 3102 ms 332252 KB Output is correct
9 Correct 2653 ms 327988 KB Output is correct
10 Correct 2723 ms 327584 KB Output is correct
11 Correct 2691 ms 327832 KB Output is correct
12 Correct 2677 ms 328584 KB Output is correct