Submission #966975

#	Time	Username	Problem	Language	Result	Execution time	Memory
966975		efedmrlr	Prize (CEOI22_prize)	C++17	100 / 100	3337 ms	494032 KiB

Main

// #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 (stderr)

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 / 10
• Subtask 2: 25 / 25
• Subtask 3: 19 / 19
• Subtask 4: 22 / 22
• Subtask 5: 24 / 24