제출 #536522

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
536522		michao	공장들 (JOI14_factories)	C++14	0 / 100	8054 ms	113432 KiB

factories

#include "factories.h"
#include <bits/stdc++.h>
#define ll long long
#define mp make_pair
#define pb push_back
#define ld long double
#define pii pair<int,int>
#define sz(x) (int)x.size()
#define piii pair<pii,pii>
#define precise cout<<fixed<<setprecision(10)
#define st first
#define nd second
#define ins insert
#define vi vector<int>
#define BOOST ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0)
using namespace std;
const int MAX=5e5+5;
const ll inf=(ll)1e18+9;
const int STALA=19;
int A[MAX][STALA];
bool blocked[MAX];
int rwdc[MAX];
int sub[MAX];
vi PC[MAX];
vector<pii> P[MAX];
ll dist[MAX];
int ojciec[MAX];
int gle[MAX];
int dfs(int u,int fa){
  sub[u]=1;
  for (auto it:P[u]) if (it.st!=fa && !blocked[it.st]) sub[u]+=dfs(it.st,u);
  return sub[u];
}
 
int find_centroid(int u,int fa,int ile){
  for (auto it:P[u]) if (it.st!=fa && !blocked[it.st] && sub[it.st]>ile/2)return find_centroid(it.st,u,ile);
  return u;
}
void centroid(int u,int fa){
  int roz=dfs(u,fa);
  int next_centroid=find_centroid(u,fa,roz);
  rwdc[next_centroid]=fa;
  blocked[next_centroid]=true;
  for (auto it:P[next_centroid]){
    if (blocked[it.st])continue;
    centroid(it.st,next_centroid); 
  }
}
 
void dfs1(int u,int fa){
  ojciec[u]=fa;
  for (auto it:P[u]) if (it.st!=fa)gle[it.st]=gle[u]+1,dist[it.st]=dist[u]+it.nd,dfs1(it.st,u);
}
 
void make(int n){
  for (int i=1;i<=n;i++)A[i][0]=ojciec[i];
  for (int i=1;i<STALA;i++) for (int j=1;j<=n;j++) A[j][i]=A[A[j][i-1]][i-1];
}
 
int lca(int a,int b){
  if (gle[a]>gle[b])swap(a,b);
  for (int i=STALA-1;i>=0;i--)if (gle[A[b][i]]>=gle[a])b=A[b][i];
  if (a==b)return a;
  for (int i=STALA-1;i>=0;i--)if (A[a][i]!=A[b][i])a=A[a][i],b=A[b][i];
  return ojciec[a];
} 
 
ll distance(int a,int b){
  return dist[b]+dist[a]-dist[lca(a,b)]*2;
} 

ll d1[MAX];
ll d2[MAX];

void Init(int N,int A[],int B[],int D[]){
	int n=N;
	for (int i=1;i<=n;i++){
		d1[i]=d2[i]=inf;
	}
	for (int i=0;i<n-1;i++){
		A[i]++;
		B[i]++;
		P[A[i]].pb(mp(B[i],D[i]));
		P[B[i]].pb(mp(A[i],D[i]));
	}
	centroid(1,-1);
	dfs1(1,1);
	make(n);
}

ll Query(int S,int X[],int T,int Y[]){
	ll ans=inf;
	for (int i=0;i<S;i++)X[i]++;
	for (int i=0;i<T;i++)Y[i]++;
	for (int i=0;i<S;i++){
		int u=X[i];
		while (u!=-1){
		//	cout<<"TERAZ "<<u<<" "<<X[i]<<" "<<distance(u,X[i])<<" "<<lca(u,X[i])<<"\n";
			d1[u]=min(d1[u],distance(u,X[i]));
			u=rwdc[u];
		}
	}
	int ile=0;
	for (int i=0;i<T;i++){
		int u=Y[i];
		ile++;
		while (u!=-1){
			d2[u]=min(d2[u],distance(u,Y[i]));
			ans=min(ans,d1[u]+d2[u]);
			u=rwdc[u];
		}
		assert(ile<=21);
	}
	
	for (int i=0;i<S;i++){
		int u=X[i];
		while (u!=-1){
		  d1[u]=inf;
		  //d2[u]=inf;
			u=rwdc[u];
		}
	}
	for (int i=0;i<T;i++){
		int u=Y[i];
		while (u!=-1){
		//	d1[u]=inf;
			d2[u]=inf;
			u=rwdc[u];
		}	
	}
	return ans;
}

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