답안 #667764

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
667764 2022-12-02T02:19:53 Z Lobo Prize (CEOI22_prize) C++17
10 / 100
3170 ms 405352 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);
        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 1640 ms 239408 KB Output is correct
2 Correct 1833 ms 240996 KB Output is correct
3 Correct 1227 ms 193628 KB Output is correct
4 Correct 1346 ms 192928 KB Output is correct
5 Correct 1256 ms 194444 KB Output is correct
6 Correct 1650 ms 203940 KB Output is correct
7 Correct 1629 ms 203900 KB Output is correct
8 Correct 1564 ms 203760 KB Output is correct
9 Correct 1221 ms 193448 KB Output is correct
10 Correct 1235 ms 194108 KB Output is correct
11 Correct 1161 ms 192448 KB Output is correct
12 Correct 1333 ms 194144 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Runtime error 1766 ms 241012 KB Execution killed with signal 13
2 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 Grader output
1 Runtime error 1203 ms 234400 KB Execution killed with signal 13
2 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 Grader output
1 Runtime error 2711 ms 398200 KB Execution killed with signal 13
2 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 Grader output
1 Runtime error 3170 ms 405352 KB Execution killed with signal 13
2 Halted 0 ms 0 KB -