oj.uz

Submission #262237

# Submission time Handle Problem Language Result Execution time Memory
262237 2020-08-12T14:10:21 Z Falcon Factories (JOI14_factories) C++14
100 / 100
 7801 ms 222388 KB 
#pragma GCC optimize("O2")

#include <bits/stdc++.h>
#include "factories.h"
#ifdef DEBUG
    #include "debug.hpp"
#endif

using namespace std;

#define all(c) (c).begin(), (c).end()
#define traverse(c, it) for(auto it = (c).begin(); it != (c).end(); it++)
#define rep(i, N) for(int i = 0; i < (N); i++)
#define rep1(i, N) for(int i = 1; i <= (N); i++)
#define rep2(i, s, e) for(int i = (s); i <= (e); i++)
#define rep3(i, s, e, d) for(int i = (s); (d) >= 0 ? i <= (e) : i >= (e); i += (d))
#define pb push_back


#ifdef DEBUG
    #define debug(x...) {dbg::depth++; string dbg_vals = dbg::to_string(x); dbg::depth--; dbg::fprint(__func__, __LINE__, #x, dbg_vals);}
    #define light_debug(x) {dbg::light = 1; dbg::dout << __func__ << ":" << __LINE__ << "  " << #x << " = " << x << endl; dbg::light = 0;}
#else
    #define debug(x...)
    #define light_debug(x) 
#endif

template<typename T>
inline T& ckmin(T& a, T b){ return a = a > b ? b : a; }

template<typename T>
inline T& ckmax(T& a, T b){ return a = a < b ? b : a; }

using ll = long long;
using pii = pair<int, int>;
using vi = vector<int>;

struct custom_hash {
    inline static uint64_t splitmix64(uint64_t x) {
        // http://xorshift.di.unimi.it/splitmix64.c
        x += 0x9e3779b97f4a7c15;
        x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
        x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
        return x ^ (x >> 31);
    }

    inline size_t operator()(uint64_t x) const {
        static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
        return splitmix64(x + FIXED_RANDOM);
    }
};

class CentroidDecomposition{
    vi size, par, done;

    int get_size(int v, int p, vector<vector<pii>>& adj){
        size[v] = 1;
        for(auto e : adj[v]){
            int u = e.first;
            if(!done[u] && u != p) size[v] += get_size(u, v, adj);
        }
        return size[v];
    }

    int get_centroid(int v, int p, int sz, vector<vector<pii>>& adj){
        for(auto e : adj[v]){
            int u = e.first;
            if(!done[u] && u != p && size[u] > sz / 2) return get_centroid(u, v, sz, adj);
        }
        return v;
    }

    void build(int v, int p, vector<vector<pii>>& adj){
        get_size(v, p, adj);
        int c = get_centroid(v, p, size[v], adj);
        par[c] = p;
        done[c] = 1;
        for(auto u : adj[c])
            if(!done[u.first]) build(u.first, c, adj);
    }

public:

    void operator()(vector<vector<pii>>& adj){
        int n = adj.size();
        done.resize(n), size.resize(n), par.resize(n);
        build(0, -1, adj);
    }

    inline int operator [](int i) const {
        return par[i];
    }
};

class TreeDist{
    int n;
    vector<ll> dist;
    vi tour, in_time, inv_in;
    vector<vi> RMQ;

    void dfs(int v, ll dis, int p, vector<vector<pii>>& adj){
        dist[v] = dis;
        in_time[v] = tour.size();
        tour.pb(in_time[v]);

        for(auto u : adj[v])
            if(u.first != p)
                dfs(u.first, dis + u.second, v, adj), tour.pb(in_time[v]);
    }

    inline int rmq(int l, int r) const {
        int k = __lg(r - l);
        return min(RMQ[l][k], RMQ[r - (1 << k)][k]);
    }

public:

    void operator()(vector<vector<pii>>& adj){
        n = adj.size();
        dist.resize(n), in_time.resize(n);
        tour.reserve(n << 1);
        dfs(0, 0, 0, adj);  

        int m = tour.size();
        inv_in.resize(m);
        rep(i, n)
            inv_in[in_time[i]] = i;

        RMQ = vector<vi>(m, vi(__lg(m + 1) + 1, m));

        rep(i, m) RMQ[i][0] = tour[i];
        rep1(k, __lg(m))
            rep(i, m){
                RMQ[i][k] = RMQ[i][k - 1];
                if(i + (1 << (k - 1)) < m) 
                    ckmin(RMQ[i][k], RMQ[i + (1 << (k - 1))][k - 1]);
            }
    }

    inline int lca(int u, int v) const {
        if(in_time[u] > in_time[v]) swap(u, v);
        return inv_in[rmq(in_time[u], in_time[v] + 1)];
    }

    inline ll distance(int u, int v) const {
        return dist[u] + dist[v] - 2 * dist[lca(u, v)];
    }
};

const ll INF = 1LL << 60;

int N;
vector<vector<pii>> adj;
CentroidDecomposition decomp;
TreeDist paths;
vector<ll> nearest;
vi upd;


void Init(int _N, int A[], int B[], int D[]) {
    #ifdef DEBUG
        freopen("debug", "w", stderr);
    #endif
    N = _N;
    adj.resize(N), nearest.resize(N);
    fill(all(nearest), INF);
    rep(i, N - 1)
        adj[A[i]].pb({B[i], D[i]}), adj[B[i]].pb({A[i], D[i]});
    decomp(adj);
    paths(adj);
}

long long Query(int S, int X[], int T, int Y[]) {
    
    auto update = [&](int v){
        for(int v_ = v; ~v; v = decomp[v])
            ckmin(nearest[v], paths.distance(v_, v)), upd.pb(v);
    }; 

    auto query = [&](int v){
        ll a = INF;
        for(int v_ = v; ~v; v = decomp[v])
            ckmin(a, nearest[v] + paths.distance(v_, v));
        return a;
    }; 

    ll ans = INF;

    rep(i, S) update(X[i]);
    rep(i, T) ckmin(ans, query(Y[i]));

    for(int i : upd) 
        nearest[i] = INF;
    upd.clear();

    return ans;
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 896 KB Output is correct
2 Correct 542 ms 12128 KB Output is correct
3 Correct 654 ms 12152 KB Output is correct
4 Correct 647 ms 12408 KB Output is correct
5 Correct 717 ms 12664 KB Output is correct
6 Correct 374 ms 12024 KB Output is correct
7 Correct 670 ms 12084 KB Output is correct
8 Correct 688 ms 12156 KB Output is correct
9 Correct 833 ms 12692 KB Output is correct
10 Correct 368 ms 12092 KB Output is correct
11 Correct 697 ms 12212 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 640 KB Output is correct
2 Correct 3582 ms 184640 KB Output is correct
3 Correct 4463 ms 188052 KB Output is correct
4 Correct 1522 ms 185444 KB Output is correct
5 Correct 6051 ms 222388 KB Output is correct
6 Correct 4728 ms 189448 KB Output is correct
7 Correct 3093 ms 44648 KB Output is correct
8 Correct 1037 ms 45012 KB Output is correct
9 Correct 3183 ms 49540 KB Output is correct
10 Correct 3422 ms 46064 KB Output is correct

Subtask #3
67.0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 896 KB Output is correct
2 Correct 542 ms 12128 KB Output is correct
3 Correct 654 ms 12152 KB Output is correct
4 Correct 647 ms 12408 KB Output is correct
5 Correct 717 ms 12664 KB Output is correct
6 Correct 374 ms 12024 KB Output is correct
7 Correct 670 ms 12084 KB Output is correct
8 Correct 688 ms 12156 KB Output is correct
9 Correct 833 ms 12692 KB Output is correct
10 Correct 368 ms 12092 KB Output is correct
11 Correct 697 ms 12212 KB Output is correct
12 Correct 3 ms 640 KB Output is correct
13 Correct 3582 ms 184640 KB Output is correct
14 Correct 4463 ms 188052 KB Output is correct
15 Correct 1522 ms 185444 KB Output is correct
16 Correct 6051 ms 222388 KB Output is correct
17 Correct 4728 ms 189448 KB Output is correct
18 Correct 3093 ms 44648 KB Output is correct
19 Correct 1037 ms 45012 KB Output is correct
20 Correct 3183 ms 49540 KB Output is correct
21 Correct 3422 ms 46064 KB Output is correct
22 Correct 5885 ms 188292 KB Output is correct
23 Correct 6696 ms 192448 KB Output is correct
24 Correct 6400 ms 193808 KB Output is correct
25 Correct 6579 ms 196496 KB Output is correct
26 Correct 6490 ms 189840 KB Output is correct
27 Correct 7801 ms 221104 KB Output is correct
28 Correct 1932 ms 214924 KB Output is correct
29 Correct 6309 ms 213752 KB Output is correct
30 Correct 6273 ms 213088 KB Output is correct
31 Correct 6143 ms 213956 KB Output is correct
32 Correct 3071 ms 65796 KB Output is correct
33 Correct 999 ms 58604 KB Output is correct
34 Correct 2257 ms 54424 KB Output is correct
35 Correct 2299 ms 54516 KB Output is correct
36 Correct 2658 ms 55184 KB Output is correct
37 Correct 2827 ms 55160 KB Output is correct