oj.uz

Submission #158492

# Submission time Handle Problem Language Result Execution time Memory
158492 2019-10-17T11:39:29 Z MvC Split the Attractions (IOI19_split) C++14
29 / 100
 2000 ms 110856 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 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<t[i].size();j++)
		{
			x=t[i][j];
			if(x==pr[i])continue;
			mx=max(mx,sub[x]);
		}
		if(mx*2<=n)
		{
			nd=i;
			break;
		}
	}
	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);
	}
	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<t[i].size();j++)
           ~^~~~~~~~~~~~
split.cpp:142:11: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(i=0;i<g[nd].size();i++)
          ~^~~~~~~~~~~~~
split.cpp:154:12: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(i=0;i<dg[pa.sc].size();i++)
           ~^~~~~~~~~~~~~~~~~
split.cpp:157: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 8 ms 7416 KB ok, correct split
2 Correct 8 ms 7416 KB ok, correct split
3 Correct 8 ms 7416 KB ok, correct split
4 Correct 8 ms 7544 KB ok, correct split
5 Correct 8 ms 7416 KB ok, correct split
6 Correct 8 ms 7412 KB ok, correct split
7 Correct 161 ms 24048 KB ok, correct split
8 Correct 150 ms 21852 KB ok, correct split
9 Correct 161 ms 21744 KB ok, correct split
10 Correct 157 ms 23736 KB ok, correct split
11 Correct 152 ms 23196 KB ok, correct split

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 7416 KB ok, correct split
2 Correct 8 ms 7416 KB ok, correct split
3 Correct 8 ms 7412 KB ok, correct split
4 Correct 182 ms 19844 KB ok, correct split
5 Correct 230 ms 18428 KB ok, correct split
6 Correct 183 ms 23792 KB ok, correct split
7 Correct 188 ms 22160 KB ok, correct split
8 Execution timed out 2077 ms 110856 KB Time limit exceeded
9 Halted 0 ms 0 KB -

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 7416 KB ok, correct split
2 Correct 150 ms 18312 KB ok, correct split
3 Correct 54 ms 11768 KB ok, correct split
4 Correct 11 ms 7416 KB ok, correct split
5 Correct 178 ms 20268 KB ok, correct split
6 Correct 161 ms 20056 KB ok, correct split
7 Correct 161 ms 20208 KB ok, correct split
8 Correct 149 ms 20976 KB ok, correct split
9 Correct 142 ms 20080 KB ok, correct split
10 Correct 46 ms 10996 KB ok, no valid answer
11 Correct 70 ms 13020 KB ok, no valid answer
12 Correct 172 ms 22512 KB ok, no valid answer
13 Correct 154 ms 18724 KB ok, no valid answer
14 Correct 200 ms 25708 KB ok, no valid answer

Subtask #4
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 7416 KB ok, correct split
2 Correct 8 ms 7416 KB ok, no valid answer
3 Correct 8 ms 7416 KB ok, correct split
4 Correct 8 ms 7420 KB ok, correct split
5 Incorrect 8 ms 7416 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 8 ms 7416 KB ok, correct split
2 Correct 8 ms 7416 KB ok, correct split
3 Correct 8 ms 7416 KB ok, correct split
4 Correct 8 ms 7544 KB ok, correct split
5 Correct 8 ms 7416 KB ok, correct split
6 Correct 8 ms 7412 KB ok, correct split
7 Correct 161 ms 24048 KB ok, correct split
8 Correct 150 ms 21852 KB ok, correct split
9 Correct 161 ms 21744 KB ok, correct split
10 Correct 157 ms 23736 KB ok, correct split
11 Correct 152 ms 23196 KB ok, correct split
12 Correct 8 ms 7416 KB ok, correct split
13 Correct 8 ms 7416 KB ok, correct split
14 Correct 8 ms 7412 KB ok, correct split
15 Correct 182 ms 19844 KB ok, correct split
16 Correct 230 ms 18428 KB ok, correct split
17 Correct 183 ms 23792 KB ok, correct split
18 Correct 188 ms 22160 KB ok, correct split
19 Execution timed out 2077 ms 110856 KB Time limit exceeded
20 Halted 0 ms 0 KB -