oj.uz

Submission #667978

# Submission time Handle Problem Language Result Execution time Memory
667978 2022-12-02T13:09:27 Z Lobo Prize (CEOI22_prize) C++17
51 / 100
 3500 ms 403104 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);
    }
}


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;
        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++) {
        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:145: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]
  145 |     for(int i = 0; i+1 < vrt.size(); i++) {
      |                    ~~~~^~~~~~~~~~~~
Main.cpp:156: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]
  156 |     for(int i = 0; i < asks.size(); i++) {
      |                    ~~^~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1625 ms 238424 KB Output is correct
2 Correct 1683 ms 238784 KB Output is correct
3 Correct 1047 ms 192008 KB Output is correct
4 Correct 1041 ms 191996 KB Output is correct
5 Correct 1020 ms 192396 KB Output is correct
6 Correct 1595 ms 202268 KB Output is correct
7 Correct 1539 ms 202132 KB Output is correct
8 Correct 1410 ms 201976 KB Output is correct
9 Correct 997 ms 192068 KB Output is correct
10 Correct 1065 ms 192384 KB Output is correct
11 Correct 993 ms 191864 KB Output is correct
12 Correct 1100 ms 192228 KB Output is correct

Subtask #2
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1742 ms 238720 KB Output is correct
2 Correct 1643 ms 238244 KB Output is correct
3 Runtime error 1054 ms 385076 KB Execution killed with signal 6
4 Halted 0 ms 0 KB -

Subtask #3
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 1177 ms 233744 KB Output is correct
2 Correct 1094 ms 233796 KB Output is correct
3 Correct 813 ms 187800 KB Output is correct
4 Correct 757 ms 187608 KB Output is correct
5 Correct 717 ms 187600 KB Output is correct
6 Correct 1000 ms 197584 KB Output is correct
7 Correct 923 ms 197736 KB Output is correct
8 Correct 1032 ms 197912 KB Output is correct
9 Correct 960 ms 195516 KB Output is correct
10 Correct 903 ms 195500 KB Output is correct
11 Correct 884 ms 195416 KB Output is correct
12 Correct 922 ms 195532 KB Output is correct

Subtask #4
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 2606 ms 398976 KB Output is correct
2 Correct 3125 ms 399040 KB Output is correct
3 Correct 1953 ms 306820 KB Output is correct
4 Correct 1788 ms 306700 KB Output is correct
5 Correct 1925 ms 306608 KB Output is correct
6 Correct 2464 ms 326568 KB Output is correct
7 Correct 2230 ms 326676 KB Output is correct
8 Correct 2206 ms 326616 KB Output is correct
9 Correct 1971 ms 322436 KB Output is correct
10 Correct 2005 ms 322476 KB Output is correct
11 Correct 1938 ms 322356 KB Output is correct
12 Correct 2009 ms 322644 KB Output is correct

Subtask #5
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 3290 ms 403104 KB Output is correct
2 Execution timed out 3531 ms 402976 KB Time limit exceeded
3 Halted 0 ms 0 KB -