oj.uz

답안 #158227

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
158227 2019-10-15T15:00:17 Z MvC Split the Attractions (IOI19_split) C++14
18 / 100
 2000 ms 16624 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=2500;
	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 2680 KB ok, correct split
4 Correct 6 ms 2680 KB ok, correct split
5 Correct 5 ms 2680 KB ok, correct split
6 Correct 5 ms 2684 KB ok, correct split
7 Correct 147 ms 16624 KB ok, correct split
8 Correct 122 ms 14828 KB ok, correct split
9 Correct 151 ms 14188 KB ok, correct split
10 Correct 149 ms 16364 KB ok, correct split
11 Correct 154 ms 15340 KB ok, correct split

Subtask #2
11.0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 2684 KB ok, correct split
2 Correct 5 ms 2680 KB ok, correct split
3 Correct 5 ms 2680 KB ok, correct split
4 Correct 139 ms 11880 KB ok, correct split
5 Correct 94 ms 10732 KB ok, correct split
6 Correct 111 ms 16428 KB ok, correct split
7 Correct 146 ms 14700 KB ok, correct split
8 Correct 174 ms 12884 KB ok, correct split
9 Correct 148 ms 10720 KB ok, correct split
10 Correct 95 ms 10988 KB ok, correct split
11 Correct 92 ms 11244 KB ok, correct split
12 Correct 79 ms 10988 KB ok, correct split

Subtask #3
0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 2680 KB ok, correct split
2 Correct 116 ms 10796 KB ok, correct split
3 Correct 36 ms 6000 KB ok, correct split
4 Correct 4 ms 2680 KB ok, correct split
5 Correct 148 ms 12780 KB ok, correct split
6 Correct 175 ms 12652 KB ok, correct split
7 Correct 161 ms 12524 KB ok, correct split
8 Correct 96 ms 13420 KB ok, correct split
9 Correct 155 ms 12268 KB ok, correct split
10 Execution timed out 2039 ms 5488 KB Time limit exceeded
11 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 4 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 6 ms 2936 KB ok, correct split
11 Correct 4 ms 2680 KB ok, correct split
12 Incorrect 986 ms 2980 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 2680 KB ok, correct split
4 Correct 6 ms 2680 KB ok, correct split
5 Correct 5 ms 2680 KB ok, correct split
6 Correct 5 ms 2684 KB ok, correct split
7 Correct 147 ms 16624 KB ok, correct split
8 Correct 122 ms 14828 KB ok, correct split
9 Correct 151 ms 14188 KB ok, correct split
10 Correct 149 ms 16364 KB ok, correct split
11 Correct 154 ms 15340 KB ok, correct split
12 Correct 4 ms 2684 KB ok, correct split
13 Correct 5 ms 2680 KB ok, correct split
14 Correct 5 ms 2680 KB ok, correct split
15 Correct 139 ms 11880 KB ok, correct split
16 Correct 94 ms 10732 KB ok, correct split
17 Correct 111 ms 16428 KB ok, correct split
18 Correct 146 ms 14700 KB ok, correct split
19 Correct 174 ms 12884 KB ok, correct split
20 Correct 148 ms 10720 KB ok, correct split
21 Correct 95 ms 10988 KB ok, correct split
22 Correct 92 ms 11244 KB ok, correct split
23 Correct 79 ms 10988 KB ok, correct split
24 Correct 4 ms 2680 KB ok, correct split
25 Correct 116 ms 10796 KB ok, correct split
26 Correct 36 ms 6000 KB ok, correct split
27 Correct 4 ms 2680 KB ok, correct split
28 Correct 148 ms 12780 KB ok, correct split
29 Correct 175 ms 12652 KB ok, correct split
30 Correct 161 ms 12524 KB ok, correct split
31 Correct 96 ms 13420 KB ok, correct split
32 Correct 155 ms 12268 KB ok, correct split
33 Execution timed out 2039 ms 5488 KB Time limit exceeded
34 Halted 0 ms 0 KB -