답안 #667771

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
667771 2022-12-02T02:46:07 Z Lobo Prize (CEOI22_prize) C++17
10 / 100
3500 ms 1048576 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();

    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);
        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:151: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]
  151 |     for(int i = 0; i+1 < vrt.size(); i++) {
      |                    ~~~~^~~~~~~~~~~~
Main.cpp:170: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]
  170 |     for(int i = 0; i < asks.size(); i++) {
      |                    ~~^~~~~~~~~~~~~
# 결과 실행 시간 메모리 Grader output
1 Correct 1858 ms 337424 KB Output is correct
2 Correct 1883 ms 340756 KB Output is correct
3 Correct 1348 ms 302584 KB Output is correct
4 Correct 1298 ms 301200 KB Output is correct
5 Correct 1370 ms 304340 KB Output is correct
6 Correct 1742 ms 310476 KB Output is correct
7 Correct 1757 ms 310624 KB Output is correct
8 Correct 1745 ms 309852 KB Output is correct
9 Correct 1288 ms 302412 KB Output is correct
10 Correct 1339 ms 303928 KB Output is correct
11 Correct 1243 ms 300284 KB Output is correct
12 Correct 1315 ms 303496 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Runtime error 1691 ms 655424 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 Grader output
1 Runtime error 1547 ms 647200 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 Grader output
1 Runtime error 2973 ms 1048576 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 Grader output
1 Execution timed out 3548 ms 1048576 KB Time limit exceeded
2 Halted 0 ms 0 KB -