oj.uz

답안 #158225

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
158225 2019-10-15T14:57:54 Z MvC Split the Attractions (IOI19_split) C++14
18 / 100
 2000 ms 17812 KB 
#include "split.h"
#pragma GCC target("avx2")
#pragma GCC optimization("O3")
#pragma GCC optimization("unroll-loops")
#include<bits/stdc++.h>
#define rc(x) return cout<<x<<endl,0
#define pb push_back
#define mkp make_pair
#define in insert
#define er erase
#define fd find
#define fr first
#define sc second
typedef long long ll;
typedef long double ld;
const ll INF=0x3f3f3f3f3f3f3f3f;
const ll llinf=(1LL<<62);
const int inf=(1<<30);
const int nmax=1e5+50;
const int mod=1e9+7;
using namespace std;
int sz[nmax],pr[nmax],a[5],b[5],n,nd,c1,c2,i,m,x,y,ts,ss[nmax],p[nmax];
vector<int>g[nmax],rs;
bitset<nmax>viz;
vector<pair<int,int> >vc;
void dfs(int x,int p)
{
	sz[x]=1;
	pr[x]=p;
	for(int i=0;i<g[x].size();i++)
	{
		int y=g[x][i];
		if(y==p)continue;
		dfs(y,x);
		sz[x]+=sz[y];
	}
	for(int i=1;i<=3;i++)
	{
		for(int j=1;j<=3;j++)
		{
			if(i==j)continue;
			if(a[i]<=sz[x] && sz[x]<=a[i]+a[j])
			{
				nd=x;
				c1=i;
				c2=6-i-j;
			}
		}
	}
}
void col(int x,int c)
{
	if(!a[c])return;
	rs[x-1]=c;
	a[c]--;
	viz[x]=1;
	for(int i=0;i<g[x].size();i++)
	{
		int y=g[x][i];
		if(y==pr[x] || viz[y])continue;
		col(y,c);
	}
}
int fnd(int x)
{
	if(p[x]==x)return x;
	return p[x]=fnd(p[x]);
}
void uni(int x,int y)
{
	if(fnd(x)!=fnd(y))
	{
		g[x].pb(y);
		g[y].pb(x);
		x=fnd(x),y=fnd(y);
		if(ss[x]<ss[y])swap(x,y);
		p[y]=x;
		ss[x]+=ss[y];
	}
}
vector<int> find_split(int N,int A,int B,int C,vector<int>P,vector<int>Q) 
{
	srand(time(0));
	n=N,b[1]=A,b[2]=B,b[3]=C,m=(int)P.size();
	for(i=0;i<m;i++)
	{
		P[i]++,Q[i]++;
		vc.pb(mkp(P[i],Q[i]));
	}
	ts=100;
	nd=-1;
	while(ts--)
	{
		for(i=1;i<=n;i++)
		{
			g[i].clear();
			viz[i]=0;
			p[i]=i;
			ss[i]=1;
		}
		for(i=1;i<=3;i++)a[i]=b[i];
		random_shuffle(vc.begin(),vc.end());
		for(i=0;i<m;i++)
		{
			x=vc[i].fr,y=vc[i].sc;
			uni(x,y);
		}
		rs.clear();
		for(i=1;i<=n;i++)rs.pb(0);
		dfs(1,0);
		if(nd!=-1)
		{
			col(nd,c1);
			col(1,c2);
			for(i=0;i<n;i++)if(!rs[i])rs[i]=6-c1-c2;
			break;
		}
	}
	return rs;
}

Compilation message

split.cpp:3:0: warning: ignoring #pragma GCC optimization [-Wunknown-pragmas]
 #pragma GCC optimization("O3")
 
split.cpp:4:0: warning: ignoring #pragma GCC optimization [-Wunknown-pragmas]
 #pragma GCC optimization("unroll-loops")
 
split.cpp: In function 'void dfs(int, int)':
split.cpp:30:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<g[x].size();i++)
              ~^~~~~~~~~~~~
split.cpp: In function 'void col(int, int)':
split.cpp:57:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<g[x].size();i++)
              ~^~~~~~~~~~~~

Subtask #1
7.0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 2680 KB ok, correct split
2 Correct 4 ms 2680 KB ok, correct split
3 Correct 4 ms 2652 KB ok, correct split
4 Correct 5 ms 2680 KB ok, correct split
5 Correct 5 ms 2680 KB ok, correct split
6 Correct 5 ms 2680 KB ok, correct split
7 Correct 128 ms 17812 KB ok, correct split
8 Correct 94 ms 15980 KB ok, correct split
9 Correct 101 ms 15340 KB ok, correct split
10 Correct 120 ms 16108 KB ok, correct split
11 Correct 131 ms 16620 KB ok, correct split

Subtask #2
11.0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 2680 KB ok, correct split
2 Correct 4 ms 2680 KB ok, correct split
3 Correct 5 ms 2680 KB ok, correct split
4 Correct 174 ms 13756 KB ok, correct split
5 Correct 92 ms 11884 KB ok, correct split
6 Correct 103 ms 14992 KB ok, correct split
7 Correct 156 ms 15852 KB ok, correct split
8 Correct 155 ms 15080 KB ok, correct split
9 Correct 109 ms 11940 KB ok, correct split
10 Correct 81 ms 11884 KB ok, correct split
11 Correct 80 ms 11756 KB ok, correct split
12 Correct 81 ms 12232 KB ok, correct split

Subtask #3
0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 2680 KB ok, correct split
2 Correct 94 ms 11964 KB ok, correct split
3 Correct 36 ms 6384 KB ok, correct split
4 Correct 5 ms 2664 KB ok, correct split
5 Correct 102 ms 13804 KB ok, correct split
6 Correct 107 ms 13732 KB ok, correct split
7 Correct 102 ms 13548 KB ok, correct split
8 Correct 104 ms 14600 KB ok, correct split
9 Correct 99 ms 13424 KB ok, correct split
10 Correct 651 ms 6000 KB ok, no valid answer
11 Correct 966 ms 7380 KB ok, no valid answer
12 Execution timed out 2048 ms 12012 KB Time limit exceeded
13 Halted 0 ms 0 KB -

Subtask #4
0 / 24.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 2680 KB ok, correct split
2 Correct 5 ms 2680 KB ok, no valid answer
3 Correct 4 ms 2680 KB ok, correct split
4 Correct 4 ms 2680 KB ok, correct split
5 Correct 4 ms 2680 KB ok, correct split
6 Correct 4 ms 2680 KB ok, correct split
7 Correct 5 ms 2680 KB ok, correct split
8 Correct 4 ms 2680 KB ok, correct split
9 Correct 6 ms 2936 KB ok, correct split
10 Correct 7 ms 2936 KB ok, correct split
11 Correct 4 ms 2680 KB ok, correct split
12 Incorrect 46 ms 3064 KB jury found a solution, contestant did not
13 Halted 0 ms 0 KB -

Subtask #5
0 / 36.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 2680 KB ok, correct split
2 Correct 4 ms 2680 KB ok, correct split
3 Correct 4 ms 2652 KB ok, correct split
4 Correct 5 ms 2680 KB ok, correct split
5 Correct 5 ms 2680 KB ok, correct split
6 Correct 5 ms 2680 KB ok, correct split
7 Correct 128 ms 17812 KB ok, correct split
8 Correct 94 ms 15980 KB ok, correct split
9 Correct 101 ms 15340 KB ok, correct split
10 Correct 120 ms 16108 KB ok, correct split
11 Correct 131 ms 16620 KB ok, correct split
12 Correct 4 ms 2680 KB ok, correct split
13 Correct 4 ms 2680 KB ok, correct split
14 Correct 5 ms 2680 KB ok, correct split
15 Correct 174 ms 13756 KB ok, correct split
16 Correct 92 ms 11884 KB ok, correct split
17 Correct 103 ms 14992 KB ok, correct split
18 Correct 156 ms 15852 KB ok, correct split
19 Correct 155 ms 15080 KB ok, correct split
20 Correct 109 ms 11940 KB ok, correct split
21 Correct 81 ms 11884 KB ok, correct split
22 Correct 80 ms 11756 KB ok, correct split
23 Correct 81 ms 12232 KB ok, correct split
24 Correct 4 ms 2680 KB ok, correct split
25 Correct 94 ms 11964 KB ok, correct split
26 Correct 36 ms 6384 KB ok, correct split
27 Correct 5 ms 2664 KB ok, correct split
28 Correct 102 ms 13804 KB ok, correct split
29 Correct 107 ms 13732 KB ok, correct split
30 Correct 102 ms 13548 KB ok, correct split
31 Correct 104 ms 14600 KB ok, correct split
32 Correct 99 ms 13424 KB ok, correct split
33 Correct 651 ms 6000 KB ok, no valid answer
34 Correct 966 ms 7380 KB ok, no valid answer
35 Execution timed out 2048 ms 12012 KB Time limit exceeded
36 Halted 0 ms 0 KB -