oj.uz

Submission #966975

# Submission time Handle Problem Language Result Execution time Memory
966975 2024-04-20T18:36:04 Z efedmrlr Prize (CEOI22_prize) C++17
100 / 100
 3337 ms 494032 KB 
// #pragma GCC optimize("O3,Ofast,unroll-loops")
// #pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#include <bits/stdc++.h>

using namespace std;


#define lli long long int
#define MP make_pair
#define pb push_back
#define REP(i,n) for(int i = 0; (i) < (n); (i)++)
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()


const int INF = 2147483600;
const int N = 1e6 + 10;
const int LGN = 21;
int n,m,q,t;

vector<vector<int> > adj1(N, vector<int>()), adj2(N, vector<int>());
int r1, r2;
vector<int> sub2, sub1;

vector<array<int,3> > pt1, pt2;
vector<vector<int> > anc1(N, vector<int>(LGN, 0)), anc2(N, vector<int>(LGN, 0));
vector<int> dep1(N, 0), dep2(N, 0);
vector<int> d1(N, INF), d2(N, INF);
void calc(vector<vector<int> > &anc) {
    for(int k = 1; k < LGN; k++) {
        for(int i = 1; i <=n; i++) {
            anc[i][k] = anc[anc[i][k - 1]][k - 1];
        }
    }
}
int kth_anc(int x, int k, vector<vector<int> > &anc) {
    for(int i = 0; i < LGN; i++) {
        if(k & (1 << i)) {
            x = anc[x][i];
        }
    }
    return x;
}

int lca(int a, int b, vector<vector<int> > &anc, vector<int> &dep) {
    if(dep[a] > dep[b]) swap(a, b);
    b = kth_anc(b, dep[b] - dep[a], anc);
    if(a == b) return a;
    for(int i = LGN - 1; i>=0; i--) {
        if(anc[a][i] != anc[b][i]) {
            a = anc[a][i]; b = anc[b][i];
        }
    }
    return anc[a][0];
}

void dfs(int node, vector<int> &ord, vector<vector<int> > &adj, vector<int> &dep) {
    ord.pb(node);
    for(auto c : adj[node]) {
        dep[c] = dep[node]  + 1;
        dfs(c, ord, adj, dep);
    }
} 
void get_d(int node, vector<vector<array<int,2> > > &adj, vector<int> &d) {
    for(auto &c : adj[node]) {
        if(d[c[0]] != INF) continue;
        d[c[0]] = d[node] + c[1]; 
        get_d(c[0], adj, d);
    }
}
inline void solve() {
    scanf("%d%d%d%d", &n, &m, &q, &t);
    for(int i = 1; i<=n; i++) {
        scanf("%d", &anc1[i][0]);
        if(anc1[i][0] == -1) {
            anc1[i][0] = i;
            r1 = i;
        }
        else {
            adj1[anc1[i][0]].pb(i);
        }
    }
    for(int i = 1; i<=n; i++) {
        scanf("%d", &anc2[i][0]);
        if(anc2[i][0] == -1) {
            anc2[i][0] = i;
            r2 = i;
        }
        else {
            adj2[anc2[i][0]].pb(i);
        }
    }
    vector<int> ord;
    dfs(r1, ord, adj1, dep1);
    for(int i = 0; i < m; i++) {
        sub2.pb(ord[i]);
        printf("%d ", ord[i]);
    }
    printf("\n");
    fflush(stdout);
    ord.clear();
    dfs(r2, ord, adj2, dep2);
    vector<int> tmp(n + 3);
    calc(anc1);
    calc(anc2);
    for(int i = 0; i < n; i++) {
        tmp[ord[i]] = i;
    }
    sub1 = sub2;
    sort(all(sub2), [&tmp](int a, int b) {
        return tmp[a] < tmp[b];
    });
    for(int i = 1; i < m; i++) {
        printf("? %d %d\n", sub2[i - 1], sub2[i]);
    }
    printf("!\n");
    fflush(stdout);
    r2 = sub2[0];
    for(int i = 1; i < m; i++) {
        array<int,4> x;
        REP(j, 4) scanf("%d", &x[j]);
        int lc = lca(sub2[i - 1], sub2[i], anc1, dep1);
        pt1.pb({sub2[i - 1], lc, x[0]});
        pt1.pb({sub2[i], lc, x[1]});
        lc = lca(sub2[i - 1], sub2[i], anc2, dep2);
        sub2.pb(lc);
        if(dep2[lc] < dep2[r2]) {
            r2 = lc;
        }
        pt2.pb({sub2[i - 1], lc, x[2]});
        pt2.pb({sub2[i], lc, x[3]});
    }
    sort(all(sub2), [&tmp](int a, int b) {
        return tmp[a] < tmp[b];
    });
    vector<vector<array<int,2> > > ad1(n + 3, vector<array<int,2> >()), ad2(n + 3, vector<array<int,2> >());
    sub2.resize(unique(all(sub2)) - sub2.begin());
    for(auto &c : pt1) {
        ad1[c[0]].pb({c[1], -c[2]});
        ad1[c[1]].pb({c[0], c[2]});
    }
    for(auto &c : pt2) {
        ad2[c[0]].pb({c[1], -c[2]});
        ad2[c[1]].pb({c[0], c[2]});
    }
    d1[r1] = d2[r2] = 0;
    get_d(r1, ad1, d1);
    get_d(r2, ad2, d2);
    vector<array<int,2> > que(t);

    REP(z, t) {
        scanf("%d%d", &que[z][0], &que[z][1]);
    }
    for(auto &c : que) {
        printf("%d %d\n", d1[c[0]] + d1[c[1]] - 2 * d1[lca(c[0], c[1], anc1, dep1)], d2[c[0]] + d2[c[1]] - 2 * d2[lca(c[0], c[1], anc2, dep2)]);
    }
    fflush(stdout);
}
 
signed main() {
    solve();    
}

Compilation message

Main.cpp: In function 'void solve()':
Main.cpp:72:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   72 |     scanf("%d%d%d%d", &n, &m, &q, &t);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:74:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   74 |         scanf("%d", &anc1[i][0]);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~
Main.cpp:84:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   84 |         scanf("%d", &anc2[i][0]);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~
Main.cpp:121:24: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  121 |         REP(j, 4) scanf("%d", &x[j]);
      |                   ~~~~~^~~~~~~~~~~~~
Main.cpp:152:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  152 |         scanf("%d%d", &que[z][0], &que[z][1]);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1751 ms 398824 KB Output is correct
2 Correct 1719 ms 403908 KB Output is correct
3 Correct 1128 ms 355308 KB Output is correct
4 Correct 1089 ms 353316 KB Output is correct
5 Correct 1154 ms 356984 KB Output is correct
6 Correct 1663 ms 366004 KB Output is correct
7 Correct 1648 ms 365184 KB Output is correct
8 Correct 1583 ms 365408 KB Output is correct
9 Correct 1108 ms 354208 KB Output is correct
10 Correct 1141 ms 357092 KB Output is correct
11 Correct 1095 ms 351884 KB Output is correct
12 Correct 1153 ms 356592 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1954 ms 403848 KB Output is correct
2 Correct 1721 ms 397740 KB Output is correct
3 Correct 1208 ms 354672 KB Output is correct
4 Correct 1257 ms 357764 KB Output is correct
5 Correct 1238 ms 355772 KB Output is correct
6 Correct 1698 ms 362360 KB Output is correct
7 Correct 1873 ms 366580 KB Output is correct
8 Correct 1871 ms 368004 KB Output is correct
9 Correct 1574 ms 366088 KB Output is correct
10 Correct 1536 ms 366272 KB Output is correct
11 Correct 1462 ms 360768 KB Output is correct
12 Correct 1564 ms 366852 KB Output is correct

Subtask #3
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 1220 ms 388372 KB Output is correct
2 Correct 1249 ms 388272 KB Output is correct
3 Correct 769 ms 342408 KB Output is correct
4 Correct 750 ms 341908 KB Output is correct
5 Correct 767 ms 342436 KB Output is correct
6 Correct 1129 ms 351820 KB Output is correct
7 Correct 1067 ms 352364 KB Output is correct
8 Correct 1094 ms 352284 KB Output is correct
9 Correct 955 ms 350512 KB Output is correct
10 Correct 949 ms 350040 KB Output is correct
11 Correct 959 ms 349800 KB Output is correct
12 Correct 907 ms 349656 KB Output is correct

Subtask #4
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 2777 ms 479256 KB Output is correct
2 Correct 2856 ms 478976 KB Output is correct
3 Correct 1701 ms 387344 KB Output is correct
4 Correct 1616 ms 386292 KB Output is correct
5 Correct 1629 ms 386568 KB Output is correct
6 Correct 2539 ms 406580 KB Output is correct
7 Correct 2515 ms 406540 KB Output is correct
8 Correct 2489 ms 406584 KB Output is correct
9 Correct 2216 ms 402668 KB Output is correct
10 Correct 2216 ms 402396 KB Output is correct
11 Correct 2166 ms 402320 KB Output is correct
12 Correct 2179 ms 402672 KB Output is correct

Subtask #5
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 3337 ms 494032 KB Output is correct
2 Correct 3283 ms 492952 KB Output is correct
3 Correct 2017 ms 397084 KB Output is correct
4 Correct 2144 ms 402880 KB Output is correct
5 Correct 1949 ms 395252 KB Output is correct
6 Correct 3310 ms 422756 KB Output is correct
7 Correct 3135 ms 415544 KB Output is correct
8 Correct 3249 ms 419488 KB Output is correct
9 Correct 2717 ms 414848 KB Output is correct
10 Correct 2638 ms 413380 KB Output is correct
11 Correct 2584 ms 413696 KB Output is correct
12 Correct 2613 ms 416080 KB Output is correct