제출 #1292608

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1292608		Minbaev	공장들 (JOI14_factories)	C++20	컴파일 에러	0 ms	0 KiB

factories

#include "factories.h"
#include <bits/stdc++.h>
using namespace std;

#define pb push_back
#define ar array

const int NN = 5e5 + 5;
int n,m,k;

struct Bit {
    int sz;
    vector<long long> t, bn;
    Bit (int n=0){
    	this->sz = n;
    	t.assign(sz * 4 + 5, 0);
    	bn.assign(sz * 4 + 5, -1LL);
    }

    void push(int tl, int tr, int v){
    	if(bn[v] == -1LL) return;
    	if(tl != tr){
    		bn[v*2] = bn[v];
    		bn[v*2+1] = bn[v];
    	}
    	t[v] = (long long)(tr - tl + 1) * bn[v];
    	bn[v] = -1LL;
    }

    void update(int tl, int tr, int v, int l, int r, long long val){
    	push(tl, tr, v);
    	if(r < l || tr < l || r < tl) return;
    	if(l <= tl && tr <= r){
    		bn[v] = val;
    		push(tl, tr, v);
    		return;
    	}
    	int tm = (tl + tr) / 2;
    	update(tl, tm, v*2, l, r, val);
    	update(tm+1, tr, v*2+1, l, r, val);
    	t[v] = t[v*2] + t[v*2+1];
    }

    void upd(int l, int r, int x){
    	if(l>r) return;
    	update(1, sz, 1, l, r, (long long)x);
    }

    long long gt(int tl, int tr, int v, int l, int r){
    	push(tl, tr, v);
    	if(r < l || tr < l || r < tl) return 0LL;
    	if(l <= tl && tr <= r){
    		return t[v];
    	}
    	int tm = (tl + tr) / 2;
    	long long a = gt(tl, tm, v*2, l, r);
    	long long b = gt(tm+1, tr, v*2+1, l, r);
    	t[v] = t[v*2] + t[v*2+1];
    	return a + b;
    }

    long long get(int l, int r){
    	if(l>r) return 0LL;
    	return gt(1, sz, 1, l, r);
    }
};

Bit t(NN);

vector<ar<long long,2>> g[NN];
vector<long long> id(NN), head(NN), id_(NN), p(NN), sz(NN), dep(NN);
int timer = 0, sum = 0;

void dfs(int x, int pr){
	p[x] = pr;
	sz[x] = 1;

	for(auto &ed : g[x]){
		int to = (int)ed[0];
		long long dist = ed[1];
		if(to == pr) continue;
		dep[to] = dep[x] + dist;
		dfs(to, x);
		sz[x] += sz[to];
	}
}

void hld(int x, int pr){
	int hv = -1;
	timer += 1; id[x] = timer; id_[timer] = x;

	for(auto &ed : g[x]){
		int to = (int)ed[0];
		if(to == pr) continue;
		if(hv == -1 || sz[hv] < sz[to]) hv = to;
	}

	if(hv != -1){
		head[hv] = head[x];
		hld(hv, x);
	}

	for(auto &ed : g[x]){
		int to = (int)ed[0];
		if(to == pr || to == hv) continue;
		head[to] = to;
		hld(to, x);
	}
}

int up(int x){
	// if edge for node x (edge parent->x) is active then top is x
	if(t.get((int)id[x], (int)id[x]) > 0) return x;

	int h = (int)head[x];
	// if entire chain head..x has no active edges, go above
	if(t.get((int)id[h], (int)id[x]) == 0){
		if(p[h] == h || p[h] == -1) return h;
		else return up((int)p[h]);
	}

	// binary search by positions in HLD to find highest node in same component
	int L = (int)id[h], R = (int)id[x];
	while(L < R){
		int M = (L + R) >> 1;
		// check edges M..R: positions (M..R] correspond to edges (node at pos M+1 .. pos R)
		// In our seg, we store edge state on position id[node] for node!=root.
		long long ones = t.get(M, R);
		if(ones == (long long)(R - M)) R = M;
		else L = M + 1;
	}
	return (int)id_[L];
}

void root(int x){
	int h = (int)head[x];
	t.upd((int)id[h], (int)id[x], 1);
	if(h == 0) return;
	if(p[h] == -1) return;
	root((int)p[h]);
}

void root2(int x){
	int h = (int)head[x];
	t.upd((int)id[h], (int)id[x], 0);
	if(h == 0) return;
	if(p[h] == -1) return;
	root2((int)p[h]);
}

void Init(int N, int A[], int B[], int D[]){
	// initialize globals and structures
	n = N;
	for(int i = 0; i < n; ++i){
		g[i].clear();
		id[i] = head[i] = id_[i] = p[i] = sz[i] = dep[i] = 0;
	}
	// read exactly N-1 edges from arrays A,B,D
	for(int i = 0;i < n-1; ++i){
		int a = A[i], b = B[i];
		int d = D[i];
		g[a].pb({b, d});
		g[b].pb({a, d});
	}

	timer = 0;
	// root at 0
	p[0] = -1;
	dep[0] = 0;
	dfs(0, -1);
	head[0] = 0;
	hld(0, -1);

	// initialize segtree size properly
	t = Bit(n);
}

long long Query(int S, int X[], int T, int Y[]) {

	for(int i = 0;i < S; ++i){
		root(X[i]);
	}

	vector<ar<long long,2>> vs;
	vs.reserve(T);
	for(int i = 0;i < T; ++i){
		int u = up(Y[i]);
		vs.pb({u, dep[Y[i]] - dep[u]});
	}

	for(int i = 0;i < S; ++i){
		root2(X[i]);
	}

	sort(vs.begin(), vs.end());
	for(int i = 0;i < (int)vs.size(); ++i){
		if(i == (int)vs.size() - 1 || vs[i+1][0] != vs[i][0]){
			t.upd((int)id[(int)vs[i][0]], (int)id[(int)vs[i][0]], (int)vs[i][1]);
			continue;
		}
		if(vs[i+1][1] > vs[i][1]) vs[i+1][1] = vs[i][1];
	}

	long long res = (long long)1e17 + 7;
	for(int i = 0;i < S; ++i){
		int u = up(X[i]);
		if(t.get((int)id[u], (int)id[u]) == 0) continue;
		res = min(res, (long long)(dep[X[i]] - dep[u]) + t.get((int)id[u], (int)id[u]));
	}
	
	for(auto &pr : vs){
		int x = (int)pr[0];
		t.upd((int)id[x], (int)id[x], 0);
	}

	return res;
}