oj.uz

Submission #667663

# Submission time Handle Problem Language Result Execution time Memory
667663 2022-12-01T21:10:54 Z Lobo Prize (CEOI22_prize) C++17
0 / 100
 1595 ms 204056 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 = 5e5+10;

int n, k, q, t, pp1[maxn][21], pp2[maxn][21], 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 <= 20; 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 = 20; i >= 0; i--) {
        if(h1[pp1[u][i]] >= h1[v]) {
            u = pp1[u][i];
        }
    }
    if(u == v) return u;

    for(int i = 20; 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 <= 20; 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 = 20; i >= 0; i--) {
        if(h2[pp2[u][i]] >= h2[v]) {
            u = pp2[u][i];
        }
    }
    if(u == v) return u;

    for(int i = 20; 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) {
    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;
    }
    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++) {
        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[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();

    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;

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

    dfsd1(r1,-1);

    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.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();
    }

}

Compilation message

Main.cpp: In function 'void solve()':
Main.cpp:144: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]
  144 |     for(int i = 0; i+1 < vrt.size(); i++) {
      |                    ~~~~^~~~~~~~~~~~
Main.cpp:155: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]
  155 |     for(int i = 0; i < asks.size(); i++) {
      |                    ~~^~~~~~~~~~~~~
Main.cpp:158:13: warning: unused variable 'l1' [-Wunused-variable]
  158 |         int l1 = lca1(u,v);
      |             ^~

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1414 ms 203036 KB Time limit exceeded (wall clock)
2 Halted 0 ms 0 KB -

Subtask #2
0 / 25.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1595 ms 204056 KB Time limit exceeded (wall clock)
2 Halted 0 ms 0 KB -

Subtask #3
0 / 19.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1067 ms 197172 KB Time limit exceeded (wall clock)
2 Halted 0 ms 0 KB -

Subtask #4
0 / 22.0

# Verdict Execution time Memory Grader output
1 Runtime error 59 ms 79544 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #5
0 / 24.0

# Verdict Execution time Memory Grader output
1 Runtime error 56 ms 78004 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -