oj.uz

Submission #954481

# Submission time Handle Problem Language Result Execution time Memory
954481 2024-03-28T03:29:20 Z GrindMachine Prize (CEOI22_prize) C++17
54 / 100
 3500 ms 412264 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;
    fflush(stdout);
    
    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 << endl;
    }

    cout << "!" << endl;
    fflush(stdout);

    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 << endl;
    }

    fflush(stdout);
}

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 2184 ms 237236 KB Output is correct
2 Correct 2195 ms 237084 KB Output is correct
3 Correct 1265 ms 220872 KB Output is correct
4 Correct 1319 ms 221288 KB Output is correct
5 Correct 1331 ms 220756 KB Output is correct
6 Correct 1830 ms 222808 KB Output is correct
7 Correct 1921 ms 223328 KB Output is correct
8 Correct 1796 ms 222756 KB Output is correct
9 Correct 1311 ms 220384 KB Output is correct
10 Correct 1292 ms 221328 KB Output is correct
11 Correct 1231 ms 220820 KB Output is correct
12 Correct 1307 ms 220836 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 2323 ms 236524 KB Output is correct
2 Correct 2312 ms 236604 KB Output is correct
3 Correct 1339 ms 221240 KB Output is correct
4 Correct 1425 ms 221320 KB Output is correct
5 Correct 1340 ms 220872 KB Output is correct
6 Correct 1984 ms 222968 KB Output is correct
7 Correct 2015 ms 223052 KB Output is correct
8 Correct 1998 ms 222852 KB Output is correct
9 Correct 1722 ms 223508 KB Output is correct
10 Correct 1776 ms 223736 KB Output is correct
11 Correct 1721 ms 223696 KB Output is correct
12 Correct 1732 ms 223604 KB Output is correct

Subtask #3
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 1777 ms 235236 KB Output is correct
2 Correct 1827 ms 235176 KB Output is correct
3 Correct 1044 ms 219152 KB Output is correct
4 Correct 998 ms 219508 KB Output is correct
5 Correct 985 ms 219312 KB Output is correct
6 Correct 1400 ms 221544 KB Output is correct
7 Correct 1352 ms 221424 KB Output is correct
8 Correct 1339 ms 221644 KB Output is correct
9 Correct 1186 ms 222032 KB Output is correct
10 Correct 1157 ms 222008 KB Output is correct
11 Correct 1173 ms 221756 KB Output is correct
12 Correct 1211 ms 221752 KB Output is correct

Subtask #4
0 / 22.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3589 ms 409324 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 3582 ms 412264 KB Time limit exceeded
2 Halted 0 ms 0 KB -