oj.uz

Submission #954482

# Submission time Handle Problem Language Result Execution time Memory
954482 2024-03-28T03:32:05 Z GrindMachine Prize (CEOI22_prize) C++17
54 / 100
 3500 ms 412240 KB 
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace std;
using namespace __gnu_pbds;

template<typename T> using Tree = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
typedef long long int ll;
typedef long double ld;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;

#define fastio ios_base::sync_with_stdio(false); cin.tie(NULL)
#define pb push_back
#define sz(a) (int)a.size()
#define setbits(x) __builtin_popcountll(x)
#define ff first
#define ss second
#define conts continue
#define ceil2(x,y) ((x+y-1)/(y))
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
#define yes cout << "Yes" << endl
#define no cout << "No" << endl

#define rep(i,n) for(int i = 0; i < n; ++i)
#define rep1(i,n) for(int i = 1; i <= n; ++i)
#define rev(i,s,e) for(int i = s; i >= e; --i)
#define trav(i,a) for(auto &i : a)

template<typename T>
void amin(T &a, T b) {
    a = min(a,b);
}

template<typename T>
void amax(T &a, T b) {
    a = max(a,b);
}

#ifdef LOCAL
#include "debug.h"
#else
#define debug(x) 42
#endif

/*

refs:
https://youtu.be/N69P-6MZor0?list=PLg_Krngrs0eC_1vn0dTjyPZMkwBOcVsgH&t=1328
edi

*/

const int MOD = 1e9 + 7;
const int N = 1e6 + 5;
const int inf1 = int(1e9) + 5;
const ll inf2 = ll(1e18) + 5;

vector<int> adj[2][N];

template<int t>
struct lca_algo {
    // LCA template (for graphs with 1-based indexing)
 
    int LOG = 1;
    vector<int> depth;
    vector<vector<int>> up;
    vector<int> tin, tout;
    vector<int> order;
    int timer = 1;
 
    lca_algo() {
 
    }
 
    lca_algo(int n, int r) {
        lca_init(n,r);
    }
 
    void lca_init(int n, int r) {
        while ((1 << LOG) < n) LOG++;
        up = vector<vector<int>>(n + 1, vector<int>(LOG, r));
        depth = vector<int>(n + 1);
        tin = vector<int>(n + 1);
        tout = vector<int>(n + 1);
 
        lca_dfs(r, -1);
    }
 
    void lca_dfs(int node, int par) {
        tin[node] = timer++;
        order.pb(node);

        trav(child, adj[t][node]) {
            if (child == par) conts;
 
            up[child][0] = node;
            rep1(j, LOG - 1) {
                up[child][j] = up[up[child][j - 1]][j - 1];
            }
 
            depth[child] = depth[node] + 1;
 
            lca_dfs(child, node);
        }
 
        tout[node] = timer-1;
    }
 
    int lift(int u, int k) {
        rep(j, LOG) {
            if (k & (1 << j)) {
                u = up[u][j];
            }
        }
 
        return u;
    }

    int query(int u, int v) {
        if (depth[u] < depth[v]) swap(u, v);
        int k = depth[u] - depth[v];
        u = lift(u, k);
 
        if (u == v) return u;
 
        rev(j, LOG - 1, 0) {
            if (up[u][j] != up[v][j]) {
                u = up[u][j];
                v = up[v][j];
            }
        }
 
        u = up[u][0];
        return u;
    }
 
    int get_dis(int u, int v) {
        int lca = query(u, v);
        return depth[u] + depth[v] - 2 * depth[lca];
    }
 
    bool is_ances(int u, int v){
        return tin[u] <= tin[v] and tout[u] >= tout[v];
    }
};

void solve(int test_case)
{
    int n,k,q,t; cin >> n >> k >> q >> t;
    vector<int> roots(2);

    rep(t,2){
        rep1(u,n){
            int p; cin >> p;
            if(p == -1){
                roots[t] = u;
            }
            else{
                adj[t][p].pb(u), adj[t][u].pb(p);
            }
        }
    }

    lca_algo<0> lca0(n,roots[0]);
    lca_algo<1> lca1(n,roots[1]);
    auto nodes = lca0.order;
    while(sz(nodes) > k) nodes.pop_back();

    rep(i,k) cout << nodes[i] << " ";
    cout << endl;

    vector<pii> ord;
    trav(u,nodes) ord.pb({lca1.tin[u],u});
    sort(all(ord));

    rep(i,k-1){
        int u = ord[i].ss, v = ord[i+1].ss;
        cout << "? " << u << " " << v << '\n';
    }

    cout << "!" << endl;

    vector<int> depth0(n+5), depth1(n+5);
    pii virtual_root = {inf1,-1};

    rep(i,k-1){
        int u = ord[i].ss, v = ord[i+1].ss;
        int l0 = lca0.query(u,v), l1 = lca1.query(u,v); 
        int d1,d2,d3,d4; cin >> d1 >> d2 >> d3 >> d4;
        depth0[l0] = depth0[u]-d1;
        depth0[v] = depth0[u]-d1+d2;
        depth1[l1] = depth1[u]-d3;
        depth1[v] = depth1[u]-d3+d4;

        pii px = {lca1.depth[l1],l1};
        amin(virtual_root,px);
    }

    // tree 0 => relative to roots[0]
    {
        int d = -depth0[roots[0]];
        rep1(u,n){
            depth0[u] += d;
        }
    }

    // tree 1 => relative to virtual_root.ss
    {
        int d = -depth1[virtual_root.ss];
        rep1(u,n){
            depth1[u] += d;
        }
    }

    vector<pii> queries(t+5);
    rep1(i,t) cin >> queries[i].ff >> queries[i].ss;

    rep1(i,t){
        auto [u,v] = queries[i];
        int l0 = lca0.query(u,v), l1 = lca1.query(u,v);
        int d0 = depth0[u]+depth0[v]-2*depth0[l0];
        int d1 = depth1[u]+depth1[v]-2*depth1[l1];
        cout << d0 << " " << d1 << '\n';
    }

    cout << endl;
}

int main()
{
    fastio;

    int t = 1;
    // cin >> t;

    rep1(i, t) {
        solve(i);
    }

    return 0;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2177 ms 237052 KB Output is correct
2 Correct 2202 ms 237124 KB Output is correct
3 Correct 1283 ms 220892 KB Output is correct
4 Correct 1269 ms 221148 KB Output is correct
5 Correct 1246 ms 221496 KB Output is correct
6 Correct 1806 ms 224100 KB Output is correct
7 Correct 1816 ms 222912 KB Output is correct
8 Correct 1830 ms 223080 KB Output is correct
9 Correct 1223 ms 220792 KB Output is correct
10 Correct 1264 ms 220716 KB Output is correct
11 Correct 1297 ms 221776 KB Output is correct
12 Correct 1333 ms 221144 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 2675 ms 236660 KB Output is correct
2 Correct 2409 ms 236780 KB Output is correct
3 Correct 1280 ms 221464 KB Output is correct
4 Correct 1315 ms 221712 KB Output is correct
5 Correct 1313 ms 221864 KB Output is correct
6 Correct 1946 ms 223368 KB Output is correct
7 Correct 2003 ms 223144 KB Output is correct
8 Correct 1941 ms 223952 KB Output is correct
9 Correct 1679 ms 224024 KB Output is correct
10 Correct 1706 ms 223460 KB Output is correct
11 Correct 1604 ms 223480 KB Output is correct
12 Correct 1662 ms 223656 KB Output is correct

Subtask #3
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 1778 ms 235704 KB Output is correct
2 Correct 1847 ms 235152 KB Output is correct
3 Correct 939 ms 220060 KB Output is correct
4 Correct 974 ms 220184 KB Output is correct
5 Correct 974 ms 219612 KB Output is correct
6 Correct 1329 ms 222008 KB Output is correct
7 Correct 1298 ms 222180 KB Output is correct
8 Correct 1381 ms 221864 KB Output is correct
9 Correct 1190 ms 222356 KB Output is correct
10 Correct 1147 ms 222028 KB Output is correct
11 Correct 1122 ms 222628 KB Output is correct
12 Correct 1209 ms 222260 KB Output is correct

Subtask #4
0 / 22.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3587 ms 412240 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
0 / 24.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3607 ms 412112 KB Time limit exceeded
2 Halted 0 ms 0 KB -