제출 #1319162

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1319162		javkhlantogs	Factories (JOI14_factories)	C++20	0 / 100	4 ms	824 KiB

factories

#include<bits/stdc++.h>
#include "factories.h"
#define ll long long
#define pll pair<ll,ll>
using namespace std;
vector<vector<pll>> e;
vector<vector<pll>> anc;
vector<ll> sz,dist;
vector<bool> rem;
ll getsz(ll u,ll p){
	sz[u]=1;
	for(auto v:e[u]){
		if(v.first==p or rem[v.first]) continue;
		sz[u]+=getsz(v.first,u);
	}
	return sz[u];
}
ll getct(ll u,ll p,ll n){
	for(auto v:e[u]){
		if(v.first==p or rem[v.first]) continue;
		if(sz[v.first]>n/2) return getct(v.first,u,n);
	}
	return u;
}
void getdist(ll u,ll p,ll ct,ll d){
	anc[u].push_back({ct,d});
	for(auto v:e[u]){
		if(v.first==p or rem[v.first]) continue;
		getdist(v.first,u,ct,d+v.second);
	}
}
void decompose(ll u){
	getsz(u,u);
	ll ct=getct(u,u,sz[u]);
	rem[ct]=1;
	for(auto v:e[ct]){
		if(rem[v.first]) continue;
		getdist(v.first,ct,ct,v.second);
	}
	for(auto v:e[ct]){
		if(rem[v.first]) continue;
		decompose(v.first);
	}
}
void Init(int n, int A[], int B[], int D[]){
	e.resize(n+1);
	rem.resize(n+1,0);
	sz.resize(n+1);
	dist.resize(n+1,1e18);
	anc.resize(n+1);
	for(ll i=0 ; i<n-1 ; i++){
		e[A[i]].push_back({B[i],D[i]});
		e[B[i]].push_back({A[i],D[i]});
	}
	decompose(0);	
}
long long Query(int S, int X[], int T, int Y[]){
	ll ans=1e18;
	int i;
	for(i=0 ; i<T ; i++){
		for(auto v:anc[Y[i]]){
			dist[v.first]=1e18;
		}
	}
	for(i=0 ; i<S ; i++){
		dist[X[i]]=0;
		for(auto v:anc[X[i]]){
			dist[v.first]=min(dist[v.first],v.second);
		}
	}
	for(i=0 ; i<T ; i++){
		for(auto v:anc[Y[i]]){
			ans=min(ans,dist[v.first]+v.second);
		}
	}
	return ans;
}

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