oj.uz

Submission #158377

# Submission time Handle Problem Language Result Execution time Memory
158377 2019-10-16T19:52:54 Z MvC Split the Attractions (IOI19_split) C++14
29 / 100
 2000 ms 112180 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<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;
		}
	}
	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:142:11: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(i=0;i<g[nd].size();i++)
          ~^~~~~~~~~~~~~
split.cpp:157:12: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(i=0;i<dg[pa.sc].size();i++)
           ~^~~~~~~~~~~~~~~~~
split.cpp:160: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 9 ms 7416 KB ok, correct split
2 Correct 8 ms 7416 KB ok, correct split
3 Correct 8 ms 7420 KB ok, correct split
4 Correct 8 ms 7416 KB ok, correct split
5 Correct 8 ms 7416 KB ok, correct split
6 Correct 8 ms 7416 KB ok, correct split
7 Correct 161 ms 24120 KB ok, correct split
8 Correct 143 ms 21872 KB ok, correct split
9 Correct 152 ms 21744 KB ok, correct split
10 Correct 166 ms 23812 KB ok, correct split
11 Correct 156 ms 23152 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 7 ms 7416 KB ok, correct split
4 Correct 248 ms 19696 KB ok, correct split
5 Correct 234 ms 18392 KB ok, correct split
6 Correct 186 ms 23792 KB ok, correct split
7 Correct 163 ms 22128 KB ok, correct split
8 Execution timed out 2041 ms 112180 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 139 ms 18296 KB ok, correct split
3 Correct 51 ms 11768 KB ok, correct split
4 Correct 8 ms 7420 KB ok, correct split
5 Correct 167 ms 20336 KB ok, correct split
6 Correct 158 ms 20080 KB ok, correct split
7 Correct 149 ms 20080 KB ok, correct split
8 Correct 156 ms 20976 KB ok, correct split
9 Correct 144 ms 20080 KB ok, correct split
10 Correct 46 ms 11000 KB ok, no valid answer
11 Correct 65 ms 12788 KB ok, no valid answer
12 Correct 164 ms 22644 KB ok, no valid answer
13 Correct 135 ms 18676 KB ok, no valid answer
14 Correct 256 ms 25808 KB ok, no valid answer

Subtask #4
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 7416 KB ok, correct split
2 Correct 9 ms 7416 KB ok, no valid answer
3 Correct 9 ms 7416 KB ok, correct split
4 Correct 9 ms 7420 KB ok, correct split
5 Incorrect 8 ms 7416 KB jury found a solution, contestant did not
6 Halted 0 ms 0 KB -

Subtask #5
0 / 36.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 7416 KB ok, correct split
2 Correct 8 ms 7416 KB ok, correct split
3 Correct 8 ms 7420 KB ok, correct split
4 Correct 8 ms 7416 KB ok, correct split
5 Correct 8 ms 7416 KB ok, correct split
6 Correct 8 ms 7416 KB ok, correct split
7 Correct 161 ms 24120 KB ok, correct split
8 Correct 143 ms 21872 KB ok, correct split
9 Correct 152 ms 21744 KB ok, correct split
10 Correct 166 ms 23812 KB ok, correct split
11 Correct 156 ms 23152 KB ok, correct split
12 Correct 8 ms 7416 KB ok, correct split
13 Correct 8 ms 7416 KB ok, correct split
14 Correct 7 ms 7416 KB ok, correct split
15 Correct 248 ms 19696 KB ok, correct split
16 Correct 234 ms 18392 KB ok, correct split
17 Correct 186 ms 23792 KB ok, correct split
18 Correct 163 ms 22128 KB ok, correct split
19 Execution timed out 2041 ms 112180 KB Time limit exceeded
20 Halted 0 ms 0 KB -