oj.uz

Submission #58359

# Submission time Handle Problem Language Result Execution time Memory
58359 2018-07-17T14:47:13 Z Yehezkiel Factories (JOI14_factories) C++11
15 / 100
 8000 ms 229504 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
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]={};
LL jarak[MAXN+5]={};
vector <pii> node[MAXN+5];
void inisLCA(int now,int _par,int _depth,LL _jarak){
	depth[now]=_depth;
	jarak[now]=_jarak;
	par[0][now]=_par;
	for(int i=1;i<logn;i++)
		par[i][now]=par[i-1][par[i-1][now]];
	for(auto v:node[now])
	{
		if(v.fi==_par)
			continue;
		inisLCA(v.fi,now,_depth+1,_jarak+v.se);
	}
}
void inisLCA(){
	inisLCA(1,0,0,0);
}
int LCA(int u,int v){
	if(depth[u]>depth[v])
		swap(u,v);
	int beda=depth[v]-depth[u];
	for(int i=0;i<logn;i++)
	{
		if(beda&(1<<i))
			v=par[i][v];
	}
	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];
}
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);
	hitungSubtree(now,-1);
	int target=subtree[now]>>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);
	}
}
void buatCtr(){
	memset(parCtr,-1,sizeof(parCtr));
	buatCtr(1,0);
}
void Init(int N,int A[],int B[],int D[]){
	for(int i=0;i<N;i++)
	{
		A[i]++;B[i]++;
		node[A[i]].eb(B[i],D[i]);
		node[B[i]].eb(A[i],D[i]);
	}
	inisLCA();
	buatCtr();
}

int lastReset[MAXN+5]={},kejadian=0;
LL registered[MAXN+5];
const LL INF=1000000000000000;
void ngeFix(int pos){
	if(lastReset[pos]!=kejadian)
		registered[pos]=INF;
	lastReset[pos]=kejadian;
}
void update(int pos){
	int now=pos;
	while(now)
	{
		ngeFix(now);
		registered[now]=min(registered[now],dist(now,pos));
		now=parCtr[now];
	}
}
LL Query(int pos){
	int now=pos;
	LL ret=INF;
	while(now)
	{
		ngeFix(now);
		ret=min(ret,registered[now]+dist(now,pos));
		now=parCtr[now];
	}
	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 40 ms 14968 KB Output is correct
2 Correct 1355 ms 32984 KB Output is correct
3 Correct 2519 ms 42588 KB Output is correct
4 Correct 2305 ms 52112 KB Output is correct
5 Correct 2352 ms 62116 KB Output is correct
6 Correct 525 ms 71080 KB Output is correct
7 Correct 2400 ms 80652 KB Output is correct
8 Correct 2390 ms 90160 KB Output is correct
9 Correct 2400 ms 99816 KB Output is correct
10 Correct 511 ms 109072 KB Output is correct
11 Correct 2533 ms 118520 KB Output is correct

Subtask #2
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 118520 KB Output is correct
2 Correct 6609 ms 210812 KB Output is correct
3 Execution timed out 8077 ms 229504 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #3
0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 14968 KB Output is correct
2 Correct 1355 ms 32984 KB Output is correct
3 Correct 2519 ms 42588 KB Output is correct
4 Correct 2305 ms 52112 KB Output is correct
5 Correct 2352 ms 62116 KB Output is correct
6 Correct 525 ms 71080 KB Output is correct
7 Correct 2400 ms 80652 KB Output is correct
8 Correct 2390 ms 90160 KB Output is correct
9 Correct 2400 ms 99816 KB Output is correct
10 Correct 511 ms 109072 KB Output is correct
11 Correct 2533 ms 118520 KB Output is correct
12 Correct 19 ms 118520 KB Output is correct
13 Correct 6609 ms 210812 KB Output is correct
14 Execution timed out 8077 ms 229504 KB Time limit exceeded
15 Halted 0 ms 0 KB -