답안 #667765

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
667765 2022-12-02T02:34:17 Z Lobo Prize (CEOI22_prize) C++17
10 / 100
3181 ms 405308 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) {
    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++) {
        // 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();
    assert(vrt[0].sc == r2);

    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++) 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)));
    }

    dfsd1(r1,-1);

    vector<pair<int,int>> ans;
    for(int i = 1; i <= t; i++) {
        int u,v; cin >> u >> v;
        assert(dist2[lca2(u,v)] != -1);
        assert(dist2[v] != -1);
        assert(dist2[u] != -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:152: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]
  152 |     for(int i = 0; i+1 < vrt.size(); i++) {
      |                    ~~~~^~~~~~~~~~~~
Main.cpp:170: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]
  170 |     for(int i = 0; i < asks.size(); i++) {
      |                    ~~^~~~~~~~~~~~~
# 결과 실행 시간 메모리 Grader output
1 Correct 1741 ms 239468 KB Output is correct
2 Correct 1781 ms 241008 KB Output is correct
3 Correct 1216 ms 193624 KB Output is correct
4 Correct 1186 ms 192936 KB Output is correct
5 Correct 1293 ms 194488 KB Output is correct
6 Correct 1610 ms 204000 KB Output is correct
7 Correct 1648 ms 203936 KB Output is correct
8 Correct 1574 ms 203832 KB Output is correct
9 Correct 1362 ms 193756 KB Output is correct
10 Correct 1313 ms 194228 KB Output is correct
11 Correct 1192 ms 192540 KB Output is correct
12 Correct 1270 ms 194096 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Runtime error 1830 ms 240840 KB Execution killed with signal 13
2 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 Grader output
1 Runtime error 1158 ms 234516 KB Execution killed with signal 13
2 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 Grader output
1 Runtime error 2630 ms 398344 KB Execution killed with signal 13
2 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 Grader output
1 Runtime error 3181 ms 405308 KB Execution killed with signal 13
2 Halted 0 ms 0 KB -