Submission #312290

#	Time	Username	Problem	Language	Result	Execution time	Memory
312290		jainbot27	Factories (JOI14_factories)	C++17	100 / 100	7911 ms	366532 KiB

factories

#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 / 15
• Subtask 2: 18 / 18
• Subtask 3: 67 / 67