oj.uz

Submission #15681

# Submission time Handle Problem Language Result Execution time Memory
15681 2015-07-15T05:06:51 Z progressive Race (IOI11_race) C++14
0 / 100
 13 ms 12944 KB 
#include "race.h"
#include <vector>
#include <queue>
#include <set>
#include <cstdio>
#include <algorithm> 
using namespace std;
static const int MAXN=262144;

static set<int> conn[MAXN];
static int H[MAXN][2];
static int L[MAXN];
static int N,K;
//N: number of city K: length of course, H, L:city and cost

static int size[MAXN];
static int maxchild[MAXN];
vector<int> ele;
int dfs(int v,int pa)
{
	ele.push_back(v);
	size[v]=1;
	maxchild[v]=0;
	for(int Eno:conn[v])
	{
		int target=H[Eno][0]^H[Eno][1]^v;
		if(target==pa) continue;
		int ret=dfs(target,v);
		maxchild[v]=max(maxchild[v],ret);
		size[v]+=ret;
	}
	return size[v];
}
int findcentroid(int v)
{
	ele.clear();
	int SZ=dfs(v,-1);
	int minv=987654321;
	int mini=v;
	for(int a:ele)
	{
		int asize=max(maxchild[a],SZ-size[a]);
		if(minv>asize)
		{
			minv=asize;
			mini=a;
		}
	}
	return mini; //amolang
}
static int ans=987654231;
//saving first and second minimum value, while first and second color is different;
int fminv[1010101];
int fminc[1010101];
int sminv[1010101];
int sminc[1010101];
vector<int> dists;
void bktk(int a,int pa,int dist,int height,int color)
{
	if(dist>K) return; //do not have to think about it
	dists.push_back(dist);
	if(fminv[dist]>height)
	{
		if(fminc[dist]!=color)
		{
			sminv[dist]=fminv[dist];
			sminc[dist]=fminc[dist];
		}
		fminv[dist]=height;
		fminc[dist]=color;
	}
	else if(sminv[dist]>height)
	{
		sminv[dist]=height;
		sminc[dist]=color;
	}
	for(int Eno: conn[a])
	{
		int target=H[Eno][0]^H[Eno][1]^a;
		int distadd=L[Eno];
		if(target==pa) continue;
		bktk(target,a,dist+distadd,height+1,color);
	}
}
void work(int v)
{
	dists.clear();
	for(int Eno: conn[v])
	{
		int target=H[Eno][0]^H[Eno][1]^v;
		int dist=L[Eno];
		bktk(target,v,dist,1,target);
	}
	sort(dists.begin(),dists.end());
	dists.resize(unique(dists.begin(),dists.end())-dists.begin());
	for(int x:dists)
	{
		if(fminc[x]!=fminc[K-x])
			ans=min(ans,fminv[x]+fminv[K-x]);
		ans=min(ans,fminv[x]+sminv[K-x]);
	}
	for(int i:dists)
	{
		fminv[i]=sminv[i]=0x3f3f3f3f;
		fminc[i]=-1,sminc[i]=-2;	
	}
	ans=min(ans,fminv[K]);
}
int best_path(int N, int K, int H[][2], int L[])
{
	::N=N, ::K=K;
	for(int i=0;i<N-1;i++)
	{
		::H[i][0]=H[i][0];
		::H[i][1]=H[i][1];
		::L[i]=L[i];
		conn[H[i][0]].insert(i);
		conn[H[i][1]].insert(i);
	}
	for(int i=0;i<=K;i++)
	{
		fminv[i]=sminv[i]=0x3f3f3f3f;
		fminc[i]=-1,sminc[i]=-2;
	}
	queue<int> Q;
	Q.push(0);
	while(!Q.empty())
	{
		int v=Q.front();
		Q.pop();
		int centroid=findcentroid(v);
		work(centroid);
		for(int v:conn[centroid])
		{
			int target=H[v][0]^H[v][1]^centroid;
			conn[target].erase(v);
			Q.push(target);
		}
		conn[centroid].clear();
	}
	if(ans>N) return -1;
	return ans;
}

Subtask #1
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 12664 KB Output is correct
2 Correct 12 ms 12772 KB Output is correct
3 Correct 13 ms 12848 KB Output is correct
4 Correct 11 ms 12848 KB Output is correct
5 Correct 11 ms 12848 KB Output is correct
6 Correct 12 ms 12848 KB Output is correct
7 Correct 13 ms 12944 KB Output is correct
8 Incorrect 11 ms 12944 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #2
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 12664 KB Output is correct
2 Correct 12 ms 12772 KB Output is correct
3 Correct 13 ms 12848 KB Output is correct
4 Correct 11 ms 12848 KB Output is correct
5 Correct 11 ms 12848 KB Output is correct
6 Correct 12 ms 12848 KB Output is correct
7 Correct 13 ms 12944 KB Output is correct
8 Incorrect 11 ms 12944 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #3
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 12664 KB Output is correct
2 Correct 12 ms 12772 KB Output is correct
3 Correct 13 ms 12848 KB Output is correct
4 Correct 11 ms 12848 KB Output is correct
5 Correct 11 ms 12848 KB Output is correct
6 Correct 12 ms 12848 KB Output is correct
7 Correct 13 ms 12944 KB Output is correct
8 Incorrect 11 ms 12944 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #4
0 / 57.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 12664 KB Output is correct
2 Correct 12 ms 12772 KB Output is correct
3 Correct 13 ms 12848 KB Output is correct
4 Correct 11 ms 12848 KB Output is correct
5 Correct 11 ms 12848 KB Output is correct
6 Correct 12 ms 12848 KB Output is correct
7 Correct 13 ms 12944 KB Output is correct
8 Incorrect 11 ms 12944 KB Output isn't correct
9 Halted 0 ms 0 KB -