oj.uz

Submission #667776

# Submission time Handle Problem Language Result Execution time Memory
667776 2022-12-02T02:52:50 Z Lobo Prize (CEOI22_prize) C++17
76 / 100
 3500 ms 599032 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<int,int>> 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(dist1[u]+dist1[v]-2*dist1[lca1(u,v)],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: 'long long int' and 'std::vector<std::pair<long long int, long long 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: 'long long int' and 'std::vector<std::pair<long long int, long long 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 1919 ms 337384 KB Output is correct
2 Correct 2015 ms 340764 KB Output is correct
3 Correct 1321 ms 305756 KB Output is correct
4 Correct 1365 ms 304212 KB Output is correct
5 Correct 1402 ms 308452 KB Output is correct
6 Correct 1823 ms 310500 KB Output is correct
7 Correct 1803 ms 310472 KB Output is correct
8 Correct 1788 ms 309912 KB Output is correct
9 Correct 1504 ms 305452 KB Output is correct
10 Correct 1355 ms 307672 KB Output is correct
11 Correct 1343 ms 303016 KB Output is correct
12 Correct 1432 ms 307228 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 2250 ms 340536 KB Output is correct
2 Correct 2227 ms 336016 KB Output is correct
3 Correct 1544 ms 305116 KB Output is correct
4 Correct 1479 ms 307284 KB Output is correct
5 Correct 1401 ms 305652 KB Output is correct
6 Correct 1997 ms 307400 KB Output is correct
7 Correct 2156 ms 310904 KB Output is correct
8 Correct 2119 ms 311108 KB Output is correct
9 Correct 1728 ms 310148 KB Output is correct
10 Correct 1820 ms 310892 KB Output is correct
11 Correct 1756 ms 306764 KB Output is correct
12 Correct 1772 ms 310808 KB Output is correct

Subtask #3
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 1365 ms 330328 KB Output is correct
2 Correct 1359 ms 330220 KB Output is correct
3 Correct 1028 ms 294244 KB Output is correct
4 Correct 993 ms 294324 KB Output is correct
5 Correct 1000 ms 294272 KB Output is correct
6 Correct 1264 ms 301336 KB Output is correct
7 Correct 1199 ms 301332 KB Output is correct
8 Correct 1215 ms 301320 KB Output is correct
9 Correct 1145 ms 299940 KB Output is correct
10 Correct 1226 ms 299916 KB Output is correct
11 Correct 1131 ms 299832 KB Output is correct
12 Correct 1260 ms 299936 KB Output is correct

Subtask #4
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 3257 ms 589628 KB Output is correct
2 Correct 3081 ms 589716 KB Output is correct
3 Correct 2139 ms 517532 KB Output is correct
4 Correct 2118 ms 517528 KB Output is correct
5 Correct 2161 ms 517444 KB Output is correct
6 Correct 2901 ms 531776 KB Output is correct
7 Correct 2740 ms 531856 KB Output is correct
8 Correct 2817 ms 531620 KB Output is correct
9 Correct 2552 ms 529028 KB Output is correct
10 Correct 2575 ms 528984 KB Output is correct
11 Correct 2511 ms 528844 KB Output is correct
12 Correct 2491 ms 528868 KB Output is correct

Subtask #5
0 / 24.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3597 ms 599032 KB Time limit exceeded
2 Halted 0 ms 0 KB -