oj.uz

Submission #158491

# Submission time Handle Problem Language Result Execution time Memory
158491 2019-10-17T11:37:17 Z MvC Split the Attractions (IOI19_split) C++14
29 / 100
 2000 ms 115844 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=3e5+50;
const int mod=1e9+7;
using namespace std;
int n,i,j,x,y,bl,nd,p[nmax],pr[nmax],sub[nmax],b[5],viz[nmax],mx,m;
vector<int>g[nmax],rs,dg[nmax],t[nmax];
pair<int,int>a[5],pa;
set<pair<int,int> >s;
void siz(int x,int p)
{
	pr[x]=p;
	sub[x]=1;
	for(int i=0;i<t[x].size();i++)
	{
		int y=t[x][i];
		if(y==p)continue;
		siz(y,x);
		sub[x]+=sub[y];
	}
}
void dfs(int x,int pp,int c)
{
	p[x]=c;
	dg[c].pb(x);
	for(int i=0;i<t[x].size();i++)
	{
		int y=t[x][i];
		if(y==pp)continue;
		dfs(y,x,c);
	}
}
int fnd(int x)
{
	if(p[x]==x)return x;
	return p[x]=fnd(p[x]);
}
void uni(int x,int y)
{
	x=fnd(x),y=fnd(y);
	if(sub[x]<sub[y])swap(x,y);
	while(!dg[y].empty())
	{
		p[dg[y].back()]=x;
		dg[x].pb(dg[y].back());
		dg[y].pop_back();
	}
	s.er(s.fd(mkp(sub[x],x)));
	sub[x]+=sub[y];
	s.in(mkp(sub[x],x));
}
void bas(int x,int y)
{
	if(fnd(x)!=fnd(y))
	{
		t[x].pb(y);
		t[y].pb(x);
		x=fnd(x),y=fnd(y);
		if(sub[x]<sub[y])swap(x,y);
		p[y]=x;
		sub[x]+=sub[y];
	}
}
void frs(int x,int p)
{
	if(!a[1].fr)return;
	a[1].fr--;
	rs[x-1]=a[1].sc;
	viz[x]=1;
	for(int i=0;i<g[x].size();i++)
	{
		int y=g[x][i];
		if(fnd(y)!=p || viz[y])continue;
		frs(y,p);
	}
}
void col(int x)
{
	if(!a[2].fr)return;
	a[2].fr--;
	rs[x-1]=a[2].sc;
	viz[x]=1;
	for(int i=0;i<g[x].size();i++)
	{
		int y=g[x][i];
		if(viz[y])continue;
		col(y);
	}
}
vector<int> find_split(int N,int A,int B,int C,vector<int>P,vector<int>Q) 
{
	n=N,b[1]=A,b[2]=B,b[3]=C,m=(int)P.size();
	for(i=1;i<=3;i++)a[i]=mkp(b[i],i);
	sort(a+1,a+4);
	for(i=1;i<=n;i++)
	{
		p[i]=i;
		sub[i]=1;
	}
	for(i=0;i<m;i++)
	{
		P[i]++,Q[i]++;
		bas(P[i],Q[i]);
		g[P[i]].pb(Q[i]);
		g[Q[i]].pb(P[i]);
	}
	for(i=0;i<n;i++)rs.pb(0);
	siz(1,0);
	for(i=1;i<=n;i++)
	{
		mx=n-sub[i];
		for(j=0;j<g[i].size();j++)
		{
			x=g[i][j];
			if(x==pr[i])continue;
			mx=max(mx,sub[x]);
		}
		if(mx*2<=n)
		{
			nd=i;
			break;
		}
	}
	if(!nd)nd=1;
	siz(nd,0);
	p[nd]=nd;
	for(i=0;i<g[nd].size();i++)
	{
		x=g[nd][i];
		s.in(mkp(sub[x],x));
		dfs(x,nd,x);
	}
	if(s.empty())return rs;
	//if(s.empty() && n==3)return rs;
	//if(s.empty())while(1);
	while((int)s.size()>2)
	{
		if(s.rbegin()->fr>=a[1].fr)break;
		pa=(*s.begin());
		s.er(s.begin());
		bl=0;
		for(i=0;i<dg[pa.sc].size();i++)
		{
			x=dg[pa.sc][i];
			for(j=0;j<g[x].size();j++)
			{
				y=g[x][j];
				if(y==nd || fnd(y)==pa.sc)continue;
				uni(x,y);
				bl=1;
				break;
			}
			if(bl)break;
		}
	}
	x=s.rbegin()->sc;
	if(sub[x]<a[1].fr)return rs;
	frs(x,x);
	col(nd);
	for(i=0;i<n;i++)if(!rs[i])rs[i]=a[3].sc;
	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 siz(int, int)':
split.cpp:30:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<t[x].size();i++)
              ~^~~~~~~~~~~~
split.cpp: In function 'void dfs(int, int, int)':
split.cpp:42:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<t[x].size();i++)
              ~^~~~~~~~~~~~
split.cpp: In function 'void frs(int, int)':
split.cpp:86: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)':
split.cpp:99:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<g[x].size();i++)
              ~^~~~~~~~~~~~
split.cpp: In function 'std::vector<int> find_split(int, int, int, int, std::vector<int>, std::vector<int>)':
split.cpp:128:12: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(j=0;j<g[i].size();j++)
           ~^~~~~~~~~~~~
split.cpp:143:11: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(i=0;i<g[nd].size();i++)
          ~^~~~~~~~~~~~~
split.cpp:158:12: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(i=0;i<dg[pa.sc].size();i++)
           ~^~~~~~~~~~~~~~~~~
split.cpp:161:13: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for(j=0;j<g[x].size();j++)
            ~^~~~~~~~~~~~

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 21496 KB ok, correct split
2 Correct 21 ms 21496 KB ok, correct split
3 Correct 21 ms 21496 KB ok, correct split
4 Correct 21 ms 21496 KB ok, correct split
5 Correct 25 ms 21496 KB ok, correct split
6 Correct 22 ms 21496 KB ok, correct split
7 Correct 255 ms 39396 KB ok, correct split
8 Correct 165 ms 37120 KB ok, correct split
9 Correct 294 ms 36976 KB ok, correct split
10 Correct 168 ms 39024 KB ok, correct split
11 Correct 169 ms 38384 KB ok, correct split

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 21496 KB ok, correct split
2 Correct 20 ms 21496 KB ok, correct split
3 Correct 24 ms 21492 KB ok, correct split
4 Correct 189 ms 35568 KB ok, correct split
5 Correct 171 ms 33648 KB ok, correct split
6 Correct 174 ms 39088 KB ok, correct split
7 Correct 252 ms 37616 KB ok, correct split
8 Execution timed out 2062 ms 115844 KB Time limit exceeded
9 Halted 0 ms 0 KB -

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 21496 KB ok, correct split
2 Correct 169 ms 33548 KB ok, correct split
3 Correct 65 ms 26236 KB ok, correct split
4 Correct 22 ms 21604 KB ok, correct split
5 Correct 158 ms 35488 KB ok, correct split
6 Correct 165 ms 35300 KB ok, correct split
7 Correct 162 ms 35312 KB ok, correct split
8 Correct 243 ms 36208 KB ok, correct split
9 Correct 241 ms 35312 KB ok, correct split
10 Correct 61 ms 25588 KB ok, no valid answer
11 Correct 81 ms 27484 KB ok, no valid answer
12 Correct 192 ms 37872 KB ok, no valid answer
13 Correct 172 ms 33908 KB ok, no valid answer
14 Correct 210 ms 41064 KB ok, no valid answer

Subtask #4
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 21496 KB ok, correct split
2 Correct 21 ms 21496 KB ok, no valid answer
3 Correct 21 ms 21496 KB ok, correct split
4 Correct 22 ms 21500 KB ok, correct split
5 Incorrect 21 ms 21496 KB invalid split: #1=11, #2=1, #3=4
6 Halted 0 ms 0 KB -

Subtask #5
0 / 36.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 21496 KB ok, correct split
2 Correct 21 ms 21496 KB ok, correct split
3 Correct 21 ms 21496 KB ok, correct split
4 Correct 21 ms 21496 KB ok, correct split
5 Correct 25 ms 21496 KB ok, correct split
6 Correct 22 ms 21496 KB ok, correct split
7 Correct 255 ms 39396 KB ok, correct split
8 Correct 165 ms 37120 KB ok, correct split
9 Correct 294 ms 36976 KB ok, correct split
10 Correct 168 ms 39024 KB ok, correct split
11 Correct 169 ms 38384 KB ok, correct split
12 Correct 24 ms 21496 KB ok, correct split
13 Correct 20 ms 21496 KB ok, correct split
14 Correct 24 ms 21492 KB ok, correct split
15 Correct 189 ms 35568 KB ok, correct split
16 Correct 171 ms 33648 KB ok, correct split
17 Correct 174 ms 39088 KB ok, correct split
18 Correct 252 ms 37616 KB ok, correct split
19 Execution timed out 2062 ms 115844 KB Time limit exceeded
20 Halted 0 ms 0 KB -