oj.uz

Submission #158494

# Submission time Handle Problem Language Result Execution time Memory
158494 2019-10-17T11:42:16 Z MvC Split the Attractions (IOI19_split) C++14
40 / 100
 322 ms 27364 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<=n/2)
		{
			nd=i;
			break;
		}
	}
	siz(nd,0);
	p[nd]=nd;
	for(i=0;i<t[nd].size();i++)
	{
		x=t[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<t[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 7416 KB ok, correct split
5 Correct 9 ms 7416 KB ok, correct split
6 Correct 8 ms 7416 KB ok, correct split
7 Correct 283 ms 24048 KB ok, correct split
8 Correct 156 ms 21840 KB ok, correct split
9 Correct 169 ms 21744 KB ok, correct split
10 Correct 172 ms 23804 KB ok, correct split
11 Correct 184 ms 23196 KB ok, correct split

Subtask #2
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 7388 KB ok, correct split
2 Correct 8 ms 7416 KB ok, correct split
3 Correct 8 ms 7416 KB ok, correct split
4 Correct 182 ms 19116 KB ok, correct split
5 Correct 160 ms 18580 KB ok, correct split
6 Correct 159 ms 23924 KB ok, correct split
7 Correct 193 ms 22132 KB ok, correct split
8 Correct 322 ms 20336 KB ok, correct split
9 Correct 160 ms 19440 KB ok, correct split
10 Correct 187 ms 26936 KB ok, correct split
11 Correct 196 ms 26856 KB ok, correct split
12 Correct 200 ms 27364 KB ok, correct split

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 7416 KB ok, correct split
2 Correct 159 ms 18292 KB ok, correct split
3 Correct 52 ms 11768 KB ok, correct split
4 Correct 10 ms 7416 KB ok, correct split
5 Correct 166 ms 20208 KB ok, correct split
6 Correct 171 ms 20108 KB ok, correct split
7 Correct 157 ms 20052 KB ok, correct split
8 Correct 153 ms 21104 KB ok, correct split
9 Correct 194 ms 20208 KB ok, correct split
10 Correct 45 ms 10996 KB ok, no valid answer
11 Correct 71 ms 12792 KB ok, no valid answer
12 Correct 172 ms 22640 KB ok, no valid answer
13 Correct 154 ms 18804 KB ok, no valid answer
14 Correct 181 ms 25768 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 7388 KB ok, correct split
5 Correct 9 ms 7400 KB ok, correct split
6 Correct 8 ms 7416 KB ok, correct split
7 Correct 8 ms 7336 KB ok, correct split
8 Correct 8 ms 7416 KB ok, correct split
9 Correct 11 ms 7672 KB ok, correct split
10 Correct 11 ms 7672 KB ok, correct split
11 Correct 8 ms 7416 KB ok, correct split
12 Runtime error 23 ms 15736 KB Execution killed with signal 11 (could be triggered by violating memory limits)
13 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 9 ms 7416 KB ok, correct split
6 Correct 8 ms 7416 KB ok, correct split
7 Correct 283 ms 24048 KB ok, correct split
8 Correct 156 ms 21840 KB ok, correct split
9 Correct 169 ms 21744 KB ok, correct split
10 Correct 172 ms 23804 KB ok, correct split
11 Correct 184 ms 23196 KB ok, correct split
12 Correct 8 ms 7388 KB ok, correct split
13 Correct 8 ms 7416 KB ok, correct split
14 Correct 8 ms 7416 KB ok, correct split
15 Correct 182 ms 19116 KB ok, correct split
16 Correct 160 ms 18580 KB ok, correct split
17 Correct 159 ms 23924 KB ok, correct split
18 Correct 193 ms 22132 KB ok, correct split
19 Correct 322 ms 20336 KB ok, correct split
20 Correct 160 ms 19440 KB ok, correct split
21 Correct 187 ms 26936 KB ok, correct split
22 Correct 196 ms 26856 KB ok, correct split
23 Correct 200 ms 27364 KB ok, correct split
24 Correct 8 ms 7416 KB ok, correct split
25 Correct 159 ms 18292 KB ok, correct split
26 Correct 52 ms 11768 KB ok, correct split
27 Correct 10 ms 7416 KB ok, correct split
28 Correct 166 ms 20208 KB ok, correct split
29 Correct 171 ms 20108 KB ok, correct split
30 Correct 157 ms 20052 KB ok, correct split
31 Correct 153 ms 21104 KB ok, correct split
32 Correct 194 ms 20208 KB ok, correct split
33 Correct 45 ms 10996 KB ok, no valid answer
34 Correct 71 ms 12792 KB ok, no valid answer
35 Correct 172 ms 22640 KB ok, no valid answer
36 Correct 154 ms 18804 KB ok, no valid answer
37 Correct 181 ms 25768 KB ok, no valid answer
38 Correct 8 ms 7416 KB ok, correct split
39 Correct 8 ms 7416 KB ok, no valid answer
40 Correct 8 ms 7416 KB ok, correct split
41 Correct 8 ms 7388 KB ok, correct split
42 Correct 9 ms 7400 KB ok, correct split
43 Correct 8 ms 7416 KB ok, correct split
44 Correct 8 ms 7336 KB ok, correct split
45 Correct 8 ms 7416 KB ok, correct split
46 Correct 11 ms 7672 KB ok, correct split
47 Correct 11 ms 7672 KB ok, correct split
48 Correct 8 ms 7416 KB ok, correct split
49 Runtime error 23 ms 15736 KB Execution killed with signal 11 (could be triggered by violating memory limits)
50 Halted 0 ms 0 KB -