oj.uz

Submission #58730

# Submission time Handle Problem Language Result Execution time Memory
58730 2018-07-19T03:43:34 Z Yehezkiel Factories (JOI14_factories) C++11
15 / 100
 8000 ms 269612 KB 
#include "factories.h"
#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define mp make_pair
#define eb emplace_back
#define pb push_back
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
typedef long long LL;
typedef long double LD;
typedef pair<int,int> pii;
const int logn=19;
const int MAXN=500000;
int par[logn+3][MAXN+5]={},depth[MAXN+5]={},n;
LL jarak[MAXN+5]={};
vector <pii> node[MAXN+5];
inline void inisLCA(int now,int _par,int _depth,LL _jarak){
	depth[now]=_depth;
	jarak[now]=_jarak;
	par[0][now]=_par;
	for(auto v:node[now])
	{
		if(v.fi==_par)
			continue;
		inisLCA(v.fi,now,_depth+1,_jarak+v.se);
	}
}
inline void inisLCA(){
	inisLCA(1,0,0,0);
	for(int j=1;j<logn;++j)
		for(int i=1;i<=n;++i)
			par[j][i]=par[j-1][par[j-1][i]];
}
inline int LCA(int u,int v){
	if(depth[u]>depth[v])
		swap(u,v);
	int beda=depth[v]-depth[u],lsone;
	while(beda)
	{
		lsone=beda&-beda;
		v=par[__builtin_popcount(lsone-1)][v];
		beda^=lsone;
	}
	if(u==v)
		return u;
	for(int i=logn-1;i>=0;--i)
	{
		if(par[i][u]!=par[i][v])
			u=par[i][u],v=par[i][v];
	}
	return par[0][u];
}
inline LL dist(int u,int v){
	return jarak[u]+jarak[v]-(jarak[LCA(u,v)]<<1);
}

int parCtr[MAXN+5]={},subtree[MAXN+5]={};
int hitungSubtree(int now,int tadi){
	assert(parCtr[now]==-1);
	subtree[now]=1;
	for(auto v:node[now])
	{
		if(v.fi==tadi||parCtr[v.fi]!=-1)
			continue;
		subtree[now]+=hitungSubtree(v.fi,now);
	}
	return subtree[now];
}
void buatCtr(int now,int tadi){
	assert(parCtr[now]==-1);
	int target=hitungSubtree(now,-1)>>1;
	
	int pilihan=-1,skipAja=tadi;
	bool lanjut=true;
	while(lanjut)
	{
		lanjut=false;
		for(auto v:node[now])
		{
			if(v.fi==skipAja||parCtr[v.fi]!=-1)
				continue;
			if(subtree[v.fi]>target)
			{
				lanjut=true;
				pilihan=v.fi;
			}
		}
		if(lanjut)
		{
			skipAja=now;
			now=pilihan;
		}
	}
	
	parCtr[now]=tadi;
	for(auto v:node[now])
	{
		if(parCtr[v.fi]==-1)
			buatCtr(v.fi,now);
	}
}
vector <LL> distPar[MAXN+5];
inline void distancePar(){
	for(int i=1;i<=n;i++)
		for(int j=i;j;j=parCtr[j])
			distPar[i].pb(dist(i,j));
}
inline void buatCtr(){
	memset(parCtr,-1,sizeof(parCtr));
	buatCtr(1,0);
	distancePar();
}
void Init(int N,int A[],int B[],int D[]){
	n=N;
	for(int i=0;i<N-1;++i)
	{
		++A[i];++B[i];
		node[A[i]].eb(B[i],D[i]);
		node[B[i]].eb(A[i],D[i]);
	}
	inisLCA();
	memset(parCtr,-1,sizeof(parCtr));
	buatCtr();
}

int lastReset[MAXN+5]={},kejadian=0;
LL registered[MAXN+5];
const LL INF=1000000000000000;
inline void ngeFix(int pos){
	if(lastReset[pos]!=kejadian)
	{
		registered[pos]=INF;
		lastReset[pos]=kejadian;
	}
}
inline void update(int pos){
	for(int i=0,now=pos;now;i++,now=parCtr[now])
	{
		ngeFix(now);
		registered[now]=min(registered[now],distPar[pos][i]);
	}
}
inline LL Query(int pos){
	LL ret=INF;
	for(int i=0,now=pos;now;i++,now=parCtr[now])
	{
		ngeFix(now);
		ret=min(ret,registered[now]+distPar[pos][i]);
	}
	return ret;
}
LL Query(int S,int X[],int T,int Y[]){
	for(int i=0;i<S;++i)	++X[i];
	for(int i=0;i<T;++i)	++Y[i];
	++kejadian;
	for(int i=0;i<S;++i)
		update(X[i]);
	LL ret=INF;
	for(int i=0;i<T;++i)
		ret=min(ret,Query(Y[i]));
	return ret;
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 38 ms 26488 KB Output is correct
2 Correct 489 ms 36052 KB Output is correct
3 Correct 487 ms 36240 KB Output is correct
4 Correct 483 ms 39048 KB Output is correct
5 Correct 530 ms 39268 KB Output is correct
6 Correct 456 ms 39268 KB Output is correct
7 Correct 581 ms 39324 KB Output is correct
8 Correct 429 ms 39324 KB Output is correct
9 Correct 513 ms 39360 KB Output is correct
10 Correct 379 ms 39360 KB Output is correct
11 Correct 534 ms 39360 KB Output is correct

Subtask #2
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 39360 KB Output is correct
2 Correct 3901 ms 178260 KB Output is correct
3 Correct 7283 ms 211140 KB Output is correct
4 Correct 1323 ms 211140 KB Output is correct
5 Execution timed out 8064 ms 269612 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #3
0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 38 ms 26488 KB Output is correct
2 Correct 489 ms 36052 KB Output is correct
3 Correct 487 ms 36240 KB Output is correct
4 Correct 483 ms 39048 KB Output is correct
5 Correct 530 ms 39268 KB Output is correct
6 Correct 456 ms 39268 KB Output is correct
7 Correct 581 ms 39324 KB Output is correct
8 Correct 429 ms 39324 KB Output is correct
9 Correct 513 ms 39360 KB Output is correct
10 Correct 379 ms 39360 KB Output is correct
11 Correct 534 ms 39360 KB Output is correct
12 Correct 26 ms 39360 KB Output is correct
13 Correct 3901 ms 178260 KB Output is correct
14 Correct 7283 ms 211140 KB Output is correct
15 Correct 1323 ms 211140 KB Output is correct
16 Execution timed out 8064 ms 269612 KB Time limit exceeded
17 Halted 0 ms 0 KB -