oj.uz

Submission #312290

# Submission time Handle Problem Language Result Execution time Memory
312290 2020-10-13T01:43:41 Z jainbot27 Factories (JOI14_factories) C++17
100 / 100
 7911 ms 366532 KB 
#include <bits/stdc++.h>
using namespace std;

#define f first
#define s second
#define pb push_back
#define ar array
#define all(x) x.begin(), x.end()
#define siz(x) (int)x.size()

#define FOR(x, y, z) for(int x = (y); x < (z); x++)
#define ROF(x, z, y) for(int x = (y-1); x >= (z); x--)
#define F0R(x, z) FOR(x, 0, z)
#define R0F(x, z) ROF(x, 0, z)
#define trav(x, y) for(auto&x:y)

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

template<class T> inline bool ckmin(T&a, T b) {return b < a ? a = b, 1 : 0;}
template<class T> inline bool ckmax(T&a, T b) {return b > a ? a = b, 1 : 0;}
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

const char nl = '\n';
const int mxN = 5e5 + 10;
const int MOD = 1e9 + 7;
const long long infLL = 1e18;

struct centroid{
    vector<vector<int>> adj;
    vector<bool> vis;
    vi par, sz;
    int n;
    void init(int _n){ n = _n; adj.resize(n); par.resize(n); sz.resize(n); vis.resize(n, 0);}
    void add(int a, int b) {adj[a].pb(b); adj[b].pb(a);}
    int find_size(int u, int p = -1) {
        if(vis[u]) return 0;
        sz[u] = 1;
        trav(v, adj[u]){
            if(v != p)
                sz[u] += find_size(v, u);
        }
        return sz[u];
    }
    int find_centroid(int u, int p, int N){
        trav(v, adj[u]){
            if(v!=p&&!vis[v]&&sz[v]>N/2)
                return find_centroid(v, u, N);
        }
        return u;
    }
    void init_centroid(int u = 0, int p = -1){
        find_size(u);
        int c = find_centroid(u, -1, sz[u]);
        vis[c] = 1;
        par[c] = p;
        trav(v, adj[c])
            if(!vis[v])
                init_centroid(v, c);
    }
}C;
#define rsz resize
#define pi pii
#define vpi vpii
#define eb emplace_back
#define sz siz
template<class T> struct RMQ { // floor(log_2(x))
	int level(int x) { return 31-__builtin_clz(x); } 
	vector<T> v; vector<vi> jmp;
	int comb(int a, int b) { // index of min
		return v[a]==v[b]?min(a,b):(v[a]<v[b]?a:b); } 
	void init(const vector<T>& _v) {
		v = _v; jmp = {vi(sz(v))}; iota(all(jmp[0]),0);
		for (int j = 1; 1<<j <= sz(v); ++j) {
			jmp.pb(vi(sz(v)-(1<<j)+1));
			F0R(i,sz(jmp[j])) jmp[j][i] = comb(jmp[j-1][i],
									jmp[j-1][i+(1<<(j-1))]);
		}
	}
	int index(int l, int r) { // get index of min element
		assert(l <= r); int d = level(r-l+1);
		return comb(jmp[d][l],jmp[d][r-(1<<d)+1]); }
	T query(int l, int r) { return v[index(l,r)]; }
};
struct LCA {
	int N; vector<vi> adj;
	vi depth, pos, par, rev; // rev is for compress
	vpi tmp; RMQ<pi> r;
	void init(int _N) { N = _N; adj.rsz(N); 
		depth = pos = par = rev = vi(N); }
	void ae(int x, int y) { adj[x].pb(y), adj[y].pb(x); }
	void dfs(int x) {
		pos[x] = sz(tmp); tmp.eb(depth[x],x); 
		trav(y,adj[x]) if (y != par[x]) {
			depth[y] = depth[par[y]=x]+1, dfs(y);
			tmp.eb(depth[x],x); }
	}
	void gen(int R = 0) { par[R] = R; dfs(R); r.init(tmp); }
	int lca(int u, int v){
		u = pos[u], v = pos[v]; if (u > v) swap(u,v);
		return r.query(u,v).s; }
	int dist(int u, int v) {
		return depth[u]+depth[v]-2*depth[lca(u,v)]; }
	vpi compress(vi S) {
		auto cmp = [&](int a, int b) { return pos[a] < pos[b]; };
		sort(all(S),cmp); R0F(i,sz(S)-1) S.pb(lca(S[i],S[i+1]));
		sort(all(S),cmp); S.erase(unique(all(S)),end(S));
		vpi ret{{0,S[0]}}; F0R(i,sz(S)) rev[S[i]] = i;
		FOR(i,1,sz(S)) ret.eb(rev[lca(S[i-1],S[i])],S[i]);
		return ret;
	}
} L;

int n, q; ll bst[mxN], dep[mxN]; vector<pair<int, ll>> adj[mxN];
void dfs(int u, int p){
    trav(v, adj[u]){
        if(v.f == p) continue;
        dep[v.f] = dep[u] + v.s;
        dfs(v.f, u);
    }
}
ll getDist(int u, int v){
    // cout << "GETDIST" << endl;
    int l = L.lca(u, v);
    // cout << u << ' ' << v << ' ' << l << endl;
    return dep[u] + dep[v] - 2 * dep[l];
}
void upd(int u, int d){
    int orig = u;
    while(u != -1){
        if(d==1)
            ckmin(bst[u], getDist(u, orig));
        else 
            bst[u] = infLL;
        u = C.par[u];
    }
}
ll qry(int u){
    int orig = u;
    ll res = infLL;
    while(u != -1){
        ckmin(res, getDist(u, orig) + bst[u]);
        u = C.par[u];
    }
    return res;
}
void Init(int N, int A[], int B[], int* D){
    n = N;
    L.init(n);
    C.init(n);
    F0R(i, n){
        bst[i] = infLL;
    }
    FOR(i, 0, n-1){
        int e1 = A[i], e2 = B[i]; ll e3 = D[i];
        adj[e1].pb({e2, e3});
        adj[e2].pb({e1, e3});
        L.ae(e1, e2);
        C.add(e1, e2);
    }
    L.dfs(0);
    dfs(0, -1);
    C.init_centroid();
    L.gen();
}
ll Query(int S, int x[], int T, int y[]){
    F0R(i, S){
        upd(x[i], 1);
    }
    ll ans = infLL;
    F0R(i, T){
        ckmin(ans, qry(y[i]));
    }
    F0R(i, S){
        upd(x[i], 0);
    }
    return ans;
}
// int32_t main(){
//     ios_base::sync_with_stdio(0); cin.tie(0);
//     int N, Q;
//     cin >> N >> Q;
//     int A[N-1], B[N-1], C[N-1];
//     F0R(i, N-1){
//         cin >> A[i] >> B[i] >> C[i];
//     }
//     Init(N, A, B, C);
//     // cout << "WE GOT HERE" << endl;
//     while(Q--){
//         int S, T;
//         cin >> S >> T;
//         int x[S], y[T];
//         F0R(i, S) cin >> x[i];
//         F0R(i, T) cin >> y[i];
//         cout << Query(S, x, T, y) << nl;
//     }
//     return 0;
// }

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 12544 KB Output is correct
2 Correct 586 ms 22560 KB Output is correct
3 Correct 759 ms 22772 KB Output is correct
4 Correct 747 ms 22588 KB Output is correct
5 Correct 765 ms 22900 KB Output is correct
6 Correct 342 ms 22520 KB Output is correct
7 Correct 748 ms 22516 KB Output is correct
8 Correct 757 ms 22716 KB Output is correct
9 Correct 762 ms 23028 KB Output is correct
10 Correct 348 ms 22696 KB Output is correct
11 Correct 746 ms 22644 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 12416 KB Output is correct
2 Correct 3821 ms 313612 KB Output is correct
3 Correct 4786 ms 315304 KB Output is correct
4 Correct 1848 ms 332600 KB Output is correct
5 Correct 6030 ms 366532 KB Output is correct
6 Correct 4963 ms 335220 KB Output is correct
7 Correct 2691 ms 91104 KB Output is correct
8 Correct 843 ms 91872 KB Output is correct
9 Correct 3003 ms 96224 KB Output is correct
10 Correct 2682 ms 92512 KB Output is correct

Subtask #3
67.0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 12544 KB Output is correct
2 Correct 586 ms 22560 KB Output is correct
3 Correct 759 ms 22772 KB Output is correct
4 Correct 747 ms 22588 KB Output is correct
5 Correct 765 ms 22900 KB Output is correct
6 Correct 342 ms 22520 KB Output is correct
7 Correct 748 ms 22516 KB Output is correct
8 Correct 757 ms 22716 KB Output is correct
9 Correct 762 ms 23028 KB Output is correct
10 Correct 348 ms 22696 KB Output is correct
11 Correct 746 ms 22644 KB Output is correct
12 Correct 11 ms 12416 KB Output is correct
13 Correct 3821 ms 313612 KB Output is correct
14 Correct 4786 ms 315304 KB Output is correct
15 Correct 1848 ms 332600 KB Output is correct
16 Correct 6030 ms 366532 KB Output is correct
17 Correct 4963 ms 335220 KB Output is correct
18 Correct 2691 ms 91104 KB Output is correct
19 Correct 843 ms 91872 KB Output is correct
20 Correct 3003 ms 96224 KB Output is correct
21 Correct 2682 ms 92512 KB Output is correct
22 Correct 5144 ms 321072 KB Output is correct
23 Correct 5264 ms 323388 KB Output is correct
24 Correct 6535 ms 341308 KB Output is correct
25 Correct 6701 ms 326724 KB Output is correct
26 Correct 7077 ms 323100 KB Output is correct
27 Correct 7911 ms 350292 KB Output is correct
28 Correct 2282 ms 324064 KB Output is correct
29 Correct 6607 ms 322752 KB Output is correct
30 Correct 6617 ms 322280 KB Output is correct
31 Correct 6627 ms 341408 KB Output is correct
32 Correct 2678 ms 97312 KB Output is correct
33 Correct 767 ms 92256 KB Output is correct
34 Correct 2066 ms 89056 KB Output is correct
35 Correct 2084 ms 89056 KB Output is correct
36 Correct 2523 ms 89568 KB Output is correct
37 Correct 2556 ms 89572 KB Output is correct