oj.uz

답안 #152868

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
152868 2019-09-10T09:27:53 Z tinjyu Split the Attractions (IOI19_split) C++14
7 / 100
 2000 ms 15472 KB 
#include "split.h"
#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <time.h> 
using namespace std;
long long int cnt=0,x1[100005],y1[100005],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];
	}
}
int dfs(int x)
{
	int g=road[x];
	tag[x]=1;
	while(g!=-1)
	{
		int now=map[g][0];
		if(tag[now]==0)
		{
			y1[cnt]=x;
			x1[cnt]=now;
			cnt++;
			dfs(now);
		}
		g=map[g][1];
	}
	return 0;
}
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;
	srand (time(NULL));

	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 qw=0;
	while(qw<n)
	{
		dfs(qw);
		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;
		}
		for(int i=0;i<n;i++)sum[i]=0;
		buildp(0,-1);
		find(0,0);
		
		if(can==1)
		{
			vector<int> res(n);
			for(int i=0;i<n;i++)
			{
				res[i]=ans[i];
				if(res[i]==0)res[i]=c[1];
			} 
			return res;
		}
		qw++;
	}
	vector<int> res(n);
}

Compilation message

split.cpp: In function 'int color(int, int)':
split.cpp:35:1: warning: control reaches end of non-void function [-Wreturn-type]
 }
 ^
split.cpp: In function 'int find(int, int)':
split.cpp:72:1: warning: control reaches end of non-void function [-Wreturn-type]
 }
 ^
split.cpp: In function 'std::vector<int> find_split(int, int, int, int, std::vector<int>, std::vector<int>)':
split.cpp:162: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 380 KB ok, correct split
3 Correct 3 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 92 ms 13816 KB ok, correct split
8 Correct 86 ms 12224 KB ok, correct split
9 Correct 84 ms 12636 KB ok, correct split
10 Correct 91 ms 13296 KB ok, correct split
11 Correct 92 ms 14072 KB ok, correct split

Subtask #2
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 3 ms 376 KB ok, correct split
4 Correct 97 ms 13148 KB ok, correct split
5 Correct 76 ms 10872 KB ok, correct split
6 Correct 68 ms 13304 KB ok, correct split
7 Correct 87 ms 12940 KB ok, correct split
8 Incorrect 103 ms 15472 KB invalid split: #1=1, #2=6, #3=99993
9 Halted 0 ms 0 KB -

Subtask #3
0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 376 KB ok, correct split
2 Correct 71 ms 10872 KB ok, correct split
3 Correct 26 ms 4516 KB ok, correct split
4 Correct 2 ms 376 KB ok, correct split
5 Correct 122 ms 11896 KB ok, correct split
6 Correct 87 ms 11784 KB ok, correct split
7 Correct 99 ms 11768 KB ok, correct split
8 Correct 81 ms 12372 KB ok, correct split
9 Correct 95 ms 11920 KB ok, correct split
10 Execution timed out 2052 ms 3448 KB Time limit exceeded
11 Halted 0 ms 0 KB -

Subtask #4
0 / 24.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 376 KB ok, correct split
2 Incorrect 2 ms 376 KB WA in grader: Invalid length of the result.
3 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 380 KB ok, correct split
3 Correct 3 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 92 ms 13816 KB ok, correct split
8 Correct 86 ms 12224 KB ok, correct split
9 Correct 84 ms 12636 KB ok, correct split
10 Correct 91 ms 13296 KB ok, correct split
11 Correct 92 ms 14072 KB ok, correct split
12 Correct 2 ms 376 KB ok, correct split
13 Correct 2 ms 376 KB ok, correct split
14 Correct 3 ms 376 KB ok, correct split
15 Correct 97 ms 13148 KB ok, correct split
16 Correct 76 ms 10872 KB ok, correct split
17 Correct 68 ms 13304 KB ok, correct split
18 Correct 87 ms 12940 KB ok, correct split
19 Incorrect 103 ms 15472 KB invalid split: #1=1, #2=6, #3=99993
20 Halted 0 ms 0 KB -