제출 #1292601

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1292601		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){
    	this->sz = n;
    	t.resize(sz * 4);
    	bn.resize(sz * 4);
    	for(int i = 0;i<sz*4;i++)bn[i] = -1;
    }

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

    void update(int tl, int tr, int v, int l, int r, int 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){
    	update(1, n, 1, l, r, x);
    }

    int 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;
    	int a = gt(tl, tm, v*2, l, r);
    	int b = gt(tm+1, tr, v*2+1, l, r);
    	t[v] = t[v*2] + t[v*2+1];

    	return a + b;
    }

    int get(int l, int r){
    	return gt(1, n, 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, sum;

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

	for(auto [to, dist] : g[x]){
		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 [to, dist] : g[x]){
		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 [to, dist] : g[x]){
		if(to == pr || to == hv)continue;
		head[to] = to;
		hld(to, x);
	}
}

int up(int x){
	if(t.get(id[x], id[x]) > 0)return x;

	int h = head[x];
	if(t.get(id[h], id[x]) == 0){
		if(p[h] == h)return h;
		else return up(p[h]);
	}

	for(int i = 19;i>=0;i--){
		int num = id[x] - (1ll << i);
		if(num < id[h])continue;
		int node = id_[num];
		if(t.get(num, id[x]) == 0){
			x = node;
		}
	}

	return p[x];
}

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

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

void Init(int N, int A[], int B[], int D[]){
	n = N;
	for(int i = 0;i<n-1;i++){
		g[A[i]].pb({B[i], D[i]});
		g[B[i]].pb({A[i], D[i]});
	}

	dfs(0, 0);
	head[0] = 0;
	hld(0, 0);
}

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;
	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<vs.size();i++){
		if(i == vs.size() - 1 || vs[i+1][0] != vs[i][0]){
			t.upd(id[vs[i][0]], id[vs[i][0]], vs[i][1]);
			continue;
		}
		vs[i+1][1] = min(vs[i+1][1], vs[i][1]);
	}

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

	return res;

}