oj.uz

Submission #158226

# Submission time Handle Problem Language Result Execution time Memory
158226 2019-10-15T14:58:48 Z MvC Split the Attractions (IOI19_split) C++14
18 / 100
 2000 ms 16560 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=5000;
	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

# Verdict Execution time Memory Grader output
1 Correct 4 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 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 110 ms 16560 KB ok, correct split
8 Correct 103 ms 14828 KB ok, correct split
9 Correct 110 ms 14188 KB ok, correct split
10 Correct 108 ms 15400 KB ok, correct split
11 Correct 119 ms 15148 KB ok, correct split

Subtask #2
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2680 KB ok, correct split
2 Correct 5 ms 2680 KB ok, correct split
3 Correct 4 ms 2680 KB ok, correct split
4 Correct 125 ms 11976 KB ok, correct split
5 Correct 95 ms 10864 KB ok, correct split
6 Correct 106 ms 14060 KB ok, correct split
7 Correct 114 ms 14572 KB ok, correct split
8 Correct 123 ms 12908 KB ok, correct split
9 Correct 110 ms 10732 KB ok, correct split
10 Correct 81 ms 11116 KB ok, correct split
11 Correct 80 ms 11092 KB ok, correct split
12 Correct 81 ms 11104 KB ok, correct split

Subtask #3
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2680 KB ok, correct split
2 Correct 111 ms 10732 KB ok, correct split
3 Correct 36 ms 6000 KB ok, correct split
4 Correct 4 ms 2684 KB ok, correct split
5 Correct 95 ms 12780 KB ok, correct split
6 Correct 95 ms 12524 KB ok, correct split
7 Correct 105 ms 12396 KB ok, correct split
8 Correct 96 ms 13420 KB ok, correct split
9 Correct 95 ms 12268 KB ok, correct split
10 Execution timed out 2057 ms 5488 KB Time limit exceeded
11 Halted 0 ms 0 KB -

Subtask #4
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2680 KB ok, correct split
2 Correct 6 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 Execution timed out 2023 ms 2992 KB Time limit exceeded
13 Halted 0 ms 0 KB -

Subtask #5
0 / 36.0

# Verdict Execution time Memory Grader output
1 Correct 4 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 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 110 ms 16560 KB ok, correct split
8 Correct 103 ms 14828 KB ok, correct split
9 Correct 110 ms 14188 KB ok, correct split
10 Correct 108 ms 15400 KB ok, correct split
11 Correct 119 ms 15148 KB ok, correct split
12 Correct 4 ms 2680 KB ok, correct split
13 Correct 5 ms 2680 KB ok, correct split
14 Correct 4 ms 2680 KB ok, correct split
15 Correct 125 ms 11976 KB ok, correct split
16 Correct 95 ms 10864 KB ok, correct split
17 Correct 106 ms 14060 KB ok, correct split
18 Correct 114 ms 14572 KB ok, correct split
19 Correct 123 ms 12908 KB ok, correct split
20 Correct 110 ms 10732 KB ok, correct split
21 Correct 81 ms 11116 KB ok, correct split
22 Correct 80 ms 11092 KB ok, correct split
23 Correct 81 ms 11104 KB ok, correct split
24 Correct 4 ms 2680 KB ok, correct split
25 Correct 111 ms 10732 KB ok, correct split
26 Correct 36 ms 6000 KB ok, correct split
27 Correct 4 ms 2684 KB ok, correct split
28 Correct 95 ms 12780 KB ok, correct split
29 Correct 95 ms 12524 KB ok, correct split
30 Correct 105 ms 12396 KB ok, correct split
31 Correct 96 ms 13420 KB ok, correct split
32 Correct 95 ms 12268 KB ok, correct split
33 Execution timed out 2057 ms 5488 KB Time limit exceeded
34 Halted 0 ms 0 KB -