oj.uz

답안 #285234

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
285234 2020-08-28T12:41:21 Z YJU 공장들 (JOI14_factories) C++14
15 / 100
 8000 ms 263664 KB 
#include<bits/stdc++.h>
#include "factories.h"
#pragma GCC optimize("unroll-loops,no-stack-protector")
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<ll,ll> pll;
const ll MOD=1e9+7;
const ll MOD2=998244353;
const ll N=5e5+5;
const ld pi=3.14159265359;
const ll INF=(1LL<<60);
#define SQ(i) ((i)*(i))
#define REP(i,n) for(ll i=0;i<n;i++)
#define REP1(i,n) for(ll i=1;i<=n;i++)
#define pb push_back
#define mp make_pair
#define X first
#define Y second
#define setp setprecision
#define lwb lower_bound
#define SZ(_a) (ll)_a.size()

ll depth[N],parent[N],cut[N],sz[N],ms[N],dis[N];
pll anc[N][21];
vector<pll> v[N];
vector<ll> lis;

ll distance(ll nda,ll ndb){
	ll tmp=0;
	if(depth[nda]<depth[ndb])swap(nda,ndb);
	for(int i=19;i>=0;i--){
		if(depth[anc[nda][i].X]>=depth[ndb]){
			tmp+=anc[nda][i].Y;
			nda=anc[nda][i].X;
		}
	}
	if(nda==ndb)return tmp;
	for(int i=19;i>=0;i--){
		if(anc[nda][i].X!=anc[ndb][i].X){
			tmp+=anc[nda][i].Y+anc[ndb][i].Y;
			nda=anc[nda][i].X;ndb=anc[ndb][i].X;
		}
	}
	return tmp+anc[nda][0].Y+anc[ndb][0].Y;
}

void PDFS(ll nd,ll pa,ll cost){
	depth[nd]=depth[pa]+1;
	anc[nd][0]=mp(pa,cost);
	REP1(i,20)anc[nd][i]=mp(anc[anc[nd][i-1].X][i-1].X,anc[nd][i-1].Y+anc[anc[nd][i-1].X][i-1].Y);
	for(auto i:v[nd]){
		if(i.X==pa)continue;
		PDFS(i.X,nd,i.Y);
	}
}

void DFS(ll id,ll par){
	sz[id]=1;ms[id]=0;
	for(auto i:v[id]){
		if(i.X==par||cut[i.X])continue;
		DFS(i.X,id);
		sz[id]+=sz[i.X];
	}
	for(auto i:v[id]){
		if(i.X==par||cut[i.X])continue;
		ms[id]=max(ms[id],sz[i.X]);
	}
	lis.pb(id);
}

void buildc(ll nd,ll pa){
	lis.clear();
	DFS(nd,0);
	ll cho=lis[0];
	for(auto i:lis)if(max(ms[cho],sz[nd]-sz[cho])>max(ms[i],sz[nd]-ms[i]))cho=i;
	parent[cho]=pa;
	cut[cho]=1;
	for(auto i:v[cho]){
		if(cut[i.X]||i.X==pa)continue;
		buildc(i.X,cho);
	}
}

void Init(int n,int A[],int B[],int D[]){
	REP1(i,n)dis[i]=INF;
	REP(i,n){
		++A[i];++B[i];
		v[B[i]].pb(mp(A[i],D[i]));
		v[A[i]].pb(mp(B[i],D[i]));
	}
	depth[0]=-1;
	PDFS(1,0,0);
	buildc(1,0);
}

ll Query(int S,int x[],int T,int y[]){
	ll ans=INF;
	REP(i,S)++x[i];
	REP(i,T)++y[i];
	REP(i,S){
		ll nd=x[i];
		while(nd){
			dis[nd]=min(dis[nd],distance(nd,x[i]));
			nd=parent[nd];
		}
	}
	REP(i,T){
		ll nd=y[i];
		while(nd){
			ans=min(ans,dis[nd]+distance(nd,y[i]));
			nd=parent[nd];
		}
	}
	REP(i,S){
		ll nd=x[i];
		while(nd){
			dis[nd]=INF;
			nd=parent[nd];
		}
	}
	return ans;
}

Subtask #1
15.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 35 ms 12920 KB Output is correct
2 Correct 1386 ms 26872 KB Output is correct
3 Correct 2722 ms 32376 KB Output is correct
4 Correct 2545 ms 32012 KB Output is correct
5 Correct 3013 ms 32504 KB Output is correct
6 Correct 579 ms 31992 KB Output is correct
7 Correct 2683 ms 32352 KB Output is correct
8 Correct 2644 ms 32512 KB Output is correct
9 Correct 3061 ms 32444 KB Output is correct
10 Correct 579 ms 32032 KB Output is correct
11 Correct 2713 ms 32376 KB Output is correct

Subtask #2
0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Correct 14 ms 12544 KB Output is correct
2 Correct 5710 ms 252236 KB Output is correct
3 Execution timed out 8089 ms 263664 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #3
0 / 67.0

# 결과 실행 시간 메모리 Grader output
1 Correct 35 ms 12920 KB Output is correct
2 Correct 1386 ms 26872 KB Output is correct
3 Correct 2722 ms 32376 KB Output is correct
4 Correct 2545 ms 32012 KB Output is correct
5 Correct 3013 ms 32504 KB Output is correct
6 Correct 579 ms 31992 KB Output is correct
7 Correct 2683 ms 32352 KB Output is correct
8 Correct 2644 ms 32512 KB Output is correct
9 Correct 3061 ms 32444 KB Output is correct
10 Correct 579 ms 32032 KB Output is correct
11 Correct 2713 ms 32376 KB Output is correct
12 Correct 14 ms 12544 KB Output is correct
13 Correct 5710 ms 252236 KB Output is correct
14 Execution timed out 8089 ms 263664 KB Time limit exceeded
15 Halted 0 ms 0 KB -