oj.uz

답안 #285254

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
285254 2020-08-28T13:54:14 Z YJU 공장들 (JOI14_factories) C++14
0 / 100
 8000 ms 167152 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<int,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()
 
int parent[N],sz[N],ms[N],lv[N],K,lis[N],L;
vector<pll> v[N];
ll dist[N][25],dis[N];

void buildd(int nd,int pa){
	for(pll i:v[nd]){
		if(i.X==pa||lv[i.X]!=-1)continue;
		dist[i.X][L]=i.Y+dist[nd][L];
		buildd(i.X,nd);
	}
}
 
void DFS(int id,int par){
	sz[id]=1;ms[id]=0;
	for(pll i:v[id]){
		if(i.X==par||lv[i.X]!=-1)continue;
		DFS(i.X,id);
		sz[id]+=sz[i.X];
	}
	for(pll i:v[id]){
		if(i.X==par||lv[i.X]!=-1)continue;
		ms[id]=max(ms[id],sz[i.X]);
	}
	lis[K++]=id;
}
 
void buildc(int nd,int pa){
	K=0;
	DFS(nd,0);
	ll cho=lis[0];
	REP(i,K){
		if(max(ms[cho],sz[nd]-sz[cho])>max(ms[lis[i]],sz[nd]-ms[lis[i]]))cho=lis[i];
	}
	
	parent[cho]=pa;
	L=lv[cho]=lv[pa]+1;
	buildd(cho,0);
	
	for(pll i:v[cho]){
		if(lv[i.X]!=-1||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],lv[i+1]=-1;
	REP(i,n-1){
		v[B[i]].pb(mp(A[i],D[i]));
		v[A[i]].pb(mp(B[i],D[i]));
	}
	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],dist[x[i]][lv[nd]]);
			nd=parent[nd];
		}
	}
	REP(i,T){
		ll nd=y[i];
		while(nd){
			ans=min(ans,dis[nd]+dist[y[i]][lv[nd]]);
			nd=parent[nd];
		}
	}
	REP(i,S){
		ll nd=x[i];
		while(nd){
			dis[nd]=INF;
			nd=parent[nd];
		}
	}
	return ans;
}

Subtask #1
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 18 ms 12544 KB Output is correct
2 Correct 401 ms 21620 KB Output is correct
3 Correct 414 ms 21624 KB Output is correct
4 Correct 413 ms 21624 KB Output is correct
5 Correct 427 ms 22136 KB Output is correct
6 Execution timed out 8026 ms 21936 KB Time limit exceeded
7 Halted 0 ms 0 KB -

Subtask #2
0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Correct 9 ms 12416 KB Output is correct
2 Correct 2771 ms 162300 KB Output is correct
3 Correct 3890 ms 167152 KB Output is correct
4 Execution timed out 8100 ms 156432 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #3
0 / 67.0

# 결과 실행 시간 메모리 Grader output
1 Correct 18 ms 12544 KB Output is correct
2 Correct 401 ms 21620 KB Output is correct
3 Correct 414 ms 21624 KB Output is correct
4 Correct 413 ms 21624 KB Output is correct
5 Correct 427 ms 22136 KB Output is correct
6 Execution timed out 8026 ms 21936 KB Time limit exceeded
7 Halted 0 ms 0 KB -