oj.uz

답안 #152861

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
152861 2019-09-10T09:11:56 Z tinjyu Split the Attractions (IOI19_split) C++14
40 / 100
 127 ms 14424 KB 
#include "split.h"
#include <iostream>
#include <stdio.h>
using namespace std;
long long int can=0,ans[100005],f[100005],s,e,stop,a[2],b[2],c[2],sum[100005],t[100005],n,m,road[100005],map[1000005][2],tag[100005];
int buildp(int x,int father)
{
	tag[x]=1;
	f[x]=father;
	sum[x]=1;
	int g=road[x];
	while(g!=-1)
	{
		int now=map[g][0];
		if(tag[now]==0)sum[x]+=buildp(now,x);
		g=map[g][1];
	}
	return sum[x];
}
int color(int x,int col)
{
	if(s==e)return 0;
	s++;
	ans[x]=col;
	int g=road[x];
	while(g!=-1)
	{
		if(s==e)return 0;
		int now=map[g][0];
		if(now!=f[x] && now!=stop)color(now,col);
		g=map[g][1];
	}
}
int find(int x,int father)
{
	if(sum[x]>=a[0] && father>=b[0])
	{	
		can=1;
		stop=f[x];
		s=0;
		e=a[0];
		color(x,a[1]);
		stop=x;
		s=0;
		e=b[0];
		color(0,b[1]);
		return 0;
	}
	if(father>=a[0] && sum[x]>=b[0])
	{
		can=1;
		stop=x;
		s=0;
		e=a[0];
		color(0,a[1]);
		stop=f[x];
		s=0;
		e=b[0];
		color(x,b[1]);
		return 0;
	}
	int g=road[x];
	while(g!=-1)
	{
		int now=map[g][0];
		if(now!=f[x])find(now,father+(sum[x]-sum[now]));
		if(can==1)return 0;
		g=map[g][1];
	}
}
 
vector<int> find_split(int N, int A, int B, int C, vector<int> p, vector<int> q) {
	a[0]=A;
	a[1]=1;
	b[0]=B;
	b[1]=2;
	c[0]=C;
	c[1]=3;
	if(b[0]<=a[0] && b[0]<=c[0])
	{
		swap(a[0],b[0]);
		swap(a[1],b[1]);
	}
	if(c[0]<=b[0] && c[0]<=a[0])
	{
		swap(a[0],c[0]);
		swap(a[1],c[1]);
	}
	if(c[0]<=b[0])
	{
		swap(b[0],c[0]);
		swap(b[1],c[1]);
	}
 
	n=N;
	m=q.size();
	for(int i=0;i<=n;i++)road[i]=-1;
	for(int i=0;i<m;i++)
	{
		map[i*2][0]=p[i];
		map[i*2][1]=road[q[i]];
		road[q[i]]=i*2;
		map[i*2+1][0]=q[i];
		map[i*2+1][1]=road[p[i]];
		road[p[i]]=i*2+1;
	}
	int cnt=0;
	int st=0,en=0;
	t[0]=2;
	tag[2]=1;
	while(st<=en)
	{
		int x=t[st];
		int g=road[x];
		while(g!=-1)
		{
			int now=map[g][0];
			if(tag[now]==0)
			{
				en++;
				p[cnt]=x;
				q[cnt]=now;
				cnt++;
				t[en]=now;
				tag[now]=1;
			}
			g=map[g][1];
		}
		st++;
	}
	for(int i=0;i<=n;i++)
	{
		road[i]=-1;
		tag[i]=0;
	}
	for(int i=0;i<cnt;i++)
	{
		map[i*2][0]=p[i];
		map[i*2][1]=road[q[i]];
		road[q[i]]=i*2;
		map[i*2+1][0]=q[i];
		map[i*2+1][1]=road[p[i]];
		road[p[i]]=i*2+1;
	}
	buildp(0,-1);
	find(0,0);
	vector<int> res(n);
	if(can==0)return res;
	for(int i=0;i<n;i++)
	{
		res[i]=ans[i];
		if(res[i]==0)res[i]=c[1];
	} 
	return res;
}

Compilation message

split.cpp: In function 'int color(int, int)':
split.cpp:33:1: warning: control reaches end of non-void function [-Wreturn-type]
 }
 ^
split.cpp: In function 'int find(int, int)':
split.cpp:70:1: warning: control reaches end of non-void function [-Wreturn-type]
 }
 ^

Subtask #1
7.0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 376 KB ok, correct split
2 Correct 2 ms 376 KB ok, correct split
3 Correct 2 ms 376 KB ok, correct split
4 Correct 2 ms 376 KB ok, correct split
5 Correct 2 ms 376 KB ok, correct split
6 Correct 2 ms 376 KB ok, correct split
7 Correct 71 ms 13048 KB ok, correct split
8 Correct 65 ms 11384 KB ok, correct split
9 Correct 69 ms 11868 KB ok, correct split
10 Correct 72 ms 11276 KB ok, correct split
11 Correct 75 ms 13060 KB ok, correct split

Subtask #2
11.0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 376 KB ok, correct split
2 Correct 2 ms 376 KB ok, correct split
3 Correct 2 ms 376 KB ok, correct split
4 Correct 84 ms 11664 KB ok, correct split
5 Correct 74 ms 10076 KB ok, correct split
6 Correct 64 ms 11384 KB ok, correct split
7 Correct 66 ms 12152 KB ok, correct split
8 Correct 127 ms 14424 KB ok, correct split
9 Correct 67 ms 10104 KB ok, correct split
10 Correct 51 ms 10104 KB ok, correct split
11 Correct 55 ms 10152 KB ok, correct split
12 Correct 54 ms 10104 KB ok, correct split

Subtask #3
22.0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 376 KB ok, correct split
2 Correct 68 ms 10152 KB ok, correct split
3 Correct 25 ms 4192 KB ok, correct split
4 Correct 2 ms 376 KB ok, correct split
5 Correct 67 ms 11100 KB ok, correct split
6 Correct 68 ms 11132 KB ok, correct split
7 Correct 65 ms 11000 KB ok, correct split
8 Correct 68 ms 11612 KB ok, correct split
9 Correct 69 ms 11128 KB ok, correct split
10 Correct 24 ms 3324 KB ok, no valid answer
11 Correct 36 ms 4856 KB ok, no valid answer
12 Correct 71 ms 9340 KB ok, no valid answer
13 Correct 68 ms 9344 KB ok, no valid answer
14 Correct 55 ms 9464 KB ok, no valid answer

Subtask #4
0 / 24.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 376 KB ok, correct split
2 Correct 2 ms 380 KB ok, no valid answer
3 Correct 2 ms 376 KB ok, correct split
4 Correct 2 ms 376 KB ok, correct split
5 Incorrect 2 ms 376 KB jury found a solution, contestant did not
6 Halted 0 ms 0 KB -

Subtask #5
0 / 36.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 376 KB ok, correct split
2 Correct 2 ms 376 KB ok, correct split
3 Correct 2 ms 376 KB ok, correct split
4 Correct 2 ms 376 KB ok, correct split
5 Correct 2 ms 376 KB ok, correct split
6 Correct 2 ms 376 KB ok, correct split
7 Correct 71 ms 13048 KB ok, correct split
8 Correct 65 ms 11384 KB ok, correct split
9 Correct 69 ms 11868 KB ok, correct split
10 Correct 72 ms 11276 KB ok, correct split
11 Correct 75 ms 13060 KB ok, correct split
12 Correct 2 ms 376 KB ok, correct split
13 Correct 2 ms 376 KB ok, correct split
14 Correct 2 ms 376 KB ok, correct split
15 Correct 84 ms 11664 KB ok, correct split
16 Correct 74 ms 10076 KB ok, correct split
17 Correct 64 ms 11384 KB ok, correct split
18 Correct 66 ms 12152 KB ok, correct split
19 Correct 127 ms 14424 KB ok, correct split
20 Correct 67 ms 10104 KB ok, correct split
21 Correct 51 ms 10104 KB ok, correct split
22 Correct 55 ms 10152 KB ok, correct split
23 Correct 54 ms 10104 KB ok, correct split
24 Correct 2 ms 376 KB ok, correct split
25 Correct 68 ms 10152 KB ok, correct split
26 Correct 25 ms 4192 KB ok, correct split
27 Correct 2 ms 376 KB ok, correct split
28 Correct 67 ms 11100 KB ok, correct split
29 Correct 68 ms 11132 KB ok, correct split
30 Correct 65 ms 11000 KB ok, correct split
31 Correct 68 ms 11612 KB ok, correct split
32 Correct 69 ms 11128 KB ok, correct split
33 Correct 24 ms 3324 KB ok, no valid answer
34 Correct 36 ms 4856 KB ok, no valid answer
35 Correct 71 ms 9340 KB ok, no valid answer
36 Correct 68 ms 9344 KB ok, no valid answer
37 Correct 55 ms 9464 KB ok, no valid answer
38 Correct 2 ms 376 KB ok, correct split
39 Correct 2 ms 380 KB ok, no valid answer
40 Correct 2 ms 376 KB ok, correct split
41 Correct 2 ms 376 KB ok, correct split
42 Incorrect 2 ms 376 KB jury found a solution, contestant did not
43 Halted 0 ms 0 KB -