oj.uz

Submission #285276

# Submission time Handle Problem Language Result Execution time Memory
285276 2020-08-28T15:07:37 Z YJU Factories (JOI14_factories) C++14
100 / 100
 5350 ms 220640 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=1e6+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 id,int par){
	for(pll i:v[id]){
		if(i.X==par||(~lv[i.X]))continue;
		dist[i.X][L]=i.Y+dist[id][L];
		buildd(i.X,id);
	}
}
 
void DFS(int id,int par){
	sz[id]=1;ms[id]=0;
	for(pll i:v[id]){
		if(i.X==par||(~lv[i.X]))continue;
		DFS(i.X,id);
		sz[id]+=sz[i.X];
		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]-sz[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])||i.X==pa)continue;
		buildc(i.X,cho);
	}
}
 
void Init(int n,int A[],int B[],int D[]){
	REP1(i,n)dis[i]=INF,lv[i]=-1;
	REP(i,n-1)++A[i],++B[i];
	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;
	vector<ll> tmp;
	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]]);
			tmp.pb(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];
		}
	}
	for(ll i:tmp)dis[i]=INF;
	return ans;
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 24320 KB Output is correct
2 Correct 400 ms 33480 KB Output is correct
3 Correct 484 ms 33528 KB Output is correct
4 Correct 489 ms 34112 KB Output is correct
5 Correct 519 ms 34204 KB Output is correct
6 Correct 301 ms 33400 KB Output is correct
7 Correct 436 ms 37152 KB Output is correct
8 Correct 447 ms 37424 KB Output is correct
9 Correct 480 ms 37948 KB Output is correct
10 Correct 309 ms 37112 KB Output is correct
11 Correct 447 ms 37240 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 24064 KB Output is correct
2 Correct 2546 ms 173944 KB Output is correct
3 Correct 3767 ms 177720 KB Output is correct
4 Correct 1020 ms 171688 KB Output is correct
5 Correct 4416 ms 218872 KB Output is correct
6 Correct 4038 ms 190124 KB Output is correct
7 Correct 1206 ms 76536 KB Output is correct
8 Correct 674 ms 75992 KB Output is correct
9 Correct 1426 ms 80888 KB Output is correct
10 Correct 1306 ms 77644 KB Output is correct

Subtask #3
67.0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 24320 KB Output is correct
2 Correct 400 ms 33480 KB Output is correct
3 Correct 484 ms 33528 KB Output is correct
4 Correct 489 ms 34112 KB Output is correct
5 Correct 519 ms 34204 KB Output is correct
6 Correct 301 ms 33400 KB Output is correct
7 Correct 436 ms 37152 KB Output is correct
8 Correct 447 ms 37424 KB Output is correct
9 Correct 480 ms 37948 KB Output is correct
10 Correct 309 ms 37112 KB Output is correct
11 Correct 447 ms 37240 KB Output is correct
12 Correct 18 ms 24064 KB Output is correct
13 Correct 2546 ms 173944 KB Output is correct
14 Correct 3767 ms 177720 KB Output is correct
15 Correct 1020 ms 171688 KB Output is correct
16 Correct 4416 ms 218872 KB Output is correct
17 Correct 4038 ms 190124 KB Output is correct
18 Correct 1206 ms 76536 KB Output is correct
19 Correct 674 ms 75992 KB Output is correct
20 Correct 1426 ms 80888 KB Output is correct
21 Correct 1306 ms 77644 KB Output is correct
22 Correct 3070 ms 185972 KB Output is correct
23 Correct 3367 ms 194344 KB Output is correct
24 Correct 4663 ms 196716 KB Output is correct
25 Correct 4902 ms 198176 KB Output is correct
26 Correct 4585 ms 182680 KB Output is correct
27 Correct 5350 ms 220640 KB Output is correct
28 Correct 1262 ms 180176 KB Output is correct
29 Correct 4537 ms 182240 KB Output is correct
30 Correct 4453 ms 181544 KB Output is correct
31 Correct 4559 ms 182212 KB Output is correct
32 Correct 1529 ms 91516 KB Output is correct
33 Correct 587 ms 75124 KB Output is correct
34 Correct 924 ms 72340 KB Output is correct
35 Correct 889 ms 72060 KB Output is correct
36 Correct 1174 ms 73092 KB Output is correct
37 Correct 1114 ms 73048 KB Output is correct