oj.uz

Submission #158375

# Submission time Handle Problem Language Result Execution time Memory
158375 2019-10-16T19:50:47 Z MvC Split the Attractions (IOI19_split) C++14
29 / 100
 2000 ms 113952 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<=n/2)
		{
			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() && 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:156:12: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(i=0;i<dg[pa.sc].size();i++)
           ~^~~~~~~~~~~~~~~~~
split.cpp:159: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 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 160 ms 24176 KB ok, correct split
8 Correct 226 ms 21872 KB ok, correct split
9 Correct 161 ms 21744 KB ok, correct split
10 Correct 147 ms 23764 KB ok, correct split
11 Correct 152 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 8 ms 7416 KB ok, correct split
4 Correct 177 ms 19764 KB ok, correct split
5 Correct 143 ms 18288 KB ok, correct split
6 Correct 211 ms 23792 KB ok, correct split
7 Correct 162 ms 22128 KB ok, correct split
8 Execution timed out 2079 ms 113952 KB Time limit exceeded
9 Halted 0 ms 0 KB -

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 7416 KB ok, correct split
2 Correct 168 ms 18324 KB ok, correct split
3 Correct 69 ms 11768 KB ok, correct split
4 Correct 9 ms 7416 KB ok, correct split
5 Correct 212 ms 20208 KB ok, correct split
6 Correct 190 ms 20076 KB ok, correct split
7 Correct 252 ms 20132 KB ok, correct split
8 Correct 247 ms 20976 KB ok, correct split
9 Correct 213 ms 20116 KB ok, correct split
10 Correct 45 ms 10996 KB ok, no valid answer
11 Correct 65 ms 12764 KB ok, no valid answer
12 Correct 154 ms 22512 KB ok, no valid answer
13 Correct 205 ms 18676 KB ok, no valid answer
14 Correct 200 ms 25836 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 7416 KB ok, correct split
5 Runtime error 18 ms 14840 KB Execution killed with signal 11 (could be triggered by violating memory limits)
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 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 160 ms 24176 KB ok, correct split
8 Correct 226 ms 21872 KB ok, correct split
9 Correct 161 ms 21744 KB ok, correct split
10 Correct 147 ms 23764 KB ok, correct split
11 Correct 152 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 8 ms 7416 KB ok, correct split
15 Correct 177 ms 19764 KB ok, correct split
16 Correct 143 ms 18288 KB ok, correct split
17 Correct 211 ms 23792 KB ok, correct split
18 Correct 162 ms 22128 KB ok, correct split
19 Execution timed out 2079 ms 113952 KB Time limit exceeded
20 Halted 0 ms 0 KB -