제출 #497747

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
497747		S2speed	공장들 (JOI14_factories)	C++17	0 / 100	116 ms	207436 KiB

factories

#include<bits/stdc++.h>
#include<factories.h>

using namespace std;

#pragma GCC optimize ("Ofast")

#define all(x) x.begin() , x.end()
#define sze(x) (ll)(x.size())
#define mp(x , y) make_pair(x , y)
#define wall cerr<<"--------------------------------------"<<endl
typedef long long int ll;
typedef pair<ll , ll> pll;
typedef pair<int , int> pii;
typedef long double db;
typedef pair<pll , ll> plll;
typedef pair<int , pii> piii;
typedef pair<pll , pll> pllll;

const ll maxn = 5e5 + 16 , md = 1e9 + 7 , inf = 2e16;

ll n;
vector<pll> adj[maxn] , s , r;
vector<ll> v , vdj[maxn];
bitset<maxn> bl , rd;
ll jad[maxn][20] , dis[maxn] , dep = 0 , st[maxn] , ft[maxn] , tme = 0 , ps[maxn] , sum = 0 , bc[maxn] , rc[maxn];

void pDFS(ll r , ll par){
	st[r] = tme++;
	dis[r] = dep++;
	ps[r] = sum;
	jad[r][0] = par;
	for(auto p : adj[r]){
		ll i = p.first , w = p.second;
		if(i == par) continue;
		sum += w;
		pDFS(i , r);
		sum -= w;
	}
	ft[r] = tme;
	dep--;
	return;
}

ll find_jad(ll v , ll d){
	d = dis[v] - d;
	for(ll j = 0 ; j < 20 ; j++){
		if(d & (1 << j)) v = jad[v][j];
	}
	return v;
}

ll lca(ll v , ll u){
	if(dis[v] > dis[u]) swap(v , u);
	u = find_jad(u , dis[v]);
	if(v == u) return v;
	for(ll j = 19 ; j >= 0 ; j--){
		if(jad[v][j] != jad[u][j]){
			v = jad[v][j];
			u = jad[u][j];
		}
	}
	return jad[v][0];
}

void Init(int N , int v[] , int u[] , int w[]){
	memset(jad , -1 , sizeof(jad));
	n = N;
	for(ll i = 0 ; i < n - 1 ; i++){
		adj[v[i]].push_back({u[i] , w[i]});
		adj[u[i]].push_back({v[i] , w[i]});
	}
	pDFS(0 , -1);
	return;
}

void cDFS(ll r){
	for(auto i : vdj[r]){
		cDFS(i);
		rc[r] = min(rc[r] , rc[i]);
		bc[r] = min(bc[r] , bc[i]);
	}
	if(rd[r]){
		rc[r] = ps[r];
	} else if(bl[r]){
		bc[r] = ps[r];
	}
	return;
}

ll Query(int k1 , int v1[] , int k2 , int v2[]){
	s.clear(); r.clear(); v.clear();
	for(ll e = 0 ; e < k1 ; e++){
		ll i = v1[e];
		s.push_back({st[i] , i});
		bl[i] = true;
	}
	for(ll e = 0 ; e < k2 ; e++){
		ll i = v2[e];
		s.push_back({st[i] , i});
		rd[i] = true;
	}
	sort(all(s)); r = s;
	ll sz = sze(s);
	for(ll e = 1 ; e < sz ; e++){
		ll i = s[e].second , j = s[e - 1].second , l = lca(i , j);
		r.push_back({st[l] , l});
	}
	sort(all(r));
	r.resize(distance(r.begin() , unique(all(r))));
	ll rs = sze(r);
	for(ll e = 0 ; e < rs ; e++){
		ll i = r[e].second , pr = -1;
		while(!v.empty()){
			ll u = v.back();
			if(st[u] < st[i] && ft[i] <= ft[u]){
				pr = u;
				break;
			}
			v.pop_back();
		}
		if(pr != -1) vdj[pr].push_back(i);
		v.push_back(i);
	}
//	cDFS(v[0]);
	ll res = inf;
	for(ll e = 0 ; e < rs ; e++){
		ll i = r[e].second;
		res = min(res , bc[i] + rc[i] - 2ll * ps[i]);
		bc[i] = rc[i] = inf;
		bl[i] = rd[i] = false;
		vdj[i].clear();
	}
	return res;
}

• Subtask 1: 0 / 15
• Subtask 2: 0 / 18
• Subtask 3: 0 / 67