oj.uz

답안 #667977

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
667977 2022-12-02T13:08:48 Z Lobo Prize (CEOI22_prize) C++17
29 / 100
 3500 ms 401012 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);
    }
}


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[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;
    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();
    dist1[r2] = 0;
    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;
        dist1[l1] = dist1[u]-d1u;
        dist1[v] = dist1[l1]+d1v;

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

    // dist1[r1] = 0;
    // dfsd1(r1,-1);

    vector<pair<long long,long long>> ans;
    for(int i = 1; i <= t; i++) {
        int u,v; cin >> u >> v;
        assert(dist1[u] != -1);
        assert(dist1[v] != -1);
        ans.pb(mp((long long) dist1[u]+dist1[v]-2*dist1[lca1(u,v)],(long long) dist2[u]+dist2[v]-2*dist2[lca2(u,v)]));
    }

    for(int i = 1; i <= t; i++) {
        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:145: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]
  145 |     for(int i = 0; i+1 < vrt.size(); i++) {
      |                    ~~~~^~~~~~~~~~~~
Main.cpp:156: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]
  156 |     for(int i = 0; i < asks.size(); i++) {
      |                    ~~^~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1688 ms 238500 KB Output is correct
2 Correct 1677 ms 238716 KB Output is correct
3 Correct 1186 ms 192084 KB Output is correct
4 Correct 1202 ms 191984 KB Output is correct
5 Correct 1181 ms 192252 KB Output is correct
6 Correct 1626 ms 202300 KB Output is correct
7 Correct 1597 ms 202068 KB Output is correct
8 Correct 1540 ms 201944 KB Output is correct
9 Correct 1161 ms 192032 KB Output is correct
10 Correct 1193 ms 192316 KB Output is correct
11 Correct 1142 ms 191800 KB Output is correct
12 Correct 1184 ms 192296 KB Output is correct

Subtask #2
0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1977 ms 238704 KB Output is correct
2 Correct 2021 ms 238136 KB Output is correct
3 Runtime error 1429 ms 384976 KB Execution killed with signal 6
4 Halted 0 ms 0 KB -

Subtask #3
19.0 / 19.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1321 ms 233784 KB Output is correct
2 Correct 1408 ms 233712 KB Output is correct
3 Correct 1014 ms 187644 KB Output is correct
4 Correct 1025 ms 187584 KB Output is correct
5 Correct 997 ms 187632 KB Output is correct
6 Correct 1273 ms 197484 KB Output is correct
7 Correct 1270 ms 197556 KB Output is correct
8 Correct 1217 ms 197588 KB Output is correct
9 Correct 1289 ms 195500 KB Output is correct
10 Correct 1052 ms 195388 KB Output is correct
11 Correct 1119 ms 195480 KB Output is correct
12 Correct 1087 ms 195420 KB Output is correct

Subtask #4
0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3373 ms 398840 KB Output is correct
2 Correct 3356 ms 399024 KB Output is correct
3 Correct 2158 ms 306948 KB Output is correct
4 Correct 2161 ms 306680 KB Output is correct
5 Correct 2176 ms 306696 KB Output is correct
6 Correct 2590 ms 326512 KB Output is correct
7 Correct 2960 ms 326740 KB Output is correct
8 Correct 2850 ms 326588 KB Output is correct
9 Correct 2731 ms 322452 KB Output is correct
10 Correct 2906 ms 322492 KB Output is correct
11 Execution timed out 3603 ms 322348 KB Time limit exceeded
12 Halted 0 ms 0 KB -

Subtask #5
0 / 24.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 3578 ms 401012 KB Time limit exceeded
2 Halted 0 ms 0 KB -