oj.uz

Submission #891509

# Submission time Handle Problem Language Result Execution time Memory
891509 2023-12-23T06:38:16 Z Faisal_Saqib Split the Attractions (IOI19_split) C++17
40 / 100
 97 ms 26248 KB 
#include <vector>
#include <set>
#include <algorithm>
using namespace std;
const int N=2e5+1;
vector<int> ma[N];
int color[N],in[N],sz[N];
bool vis[N];
set<int> one,two;
int n;
void dfs_sz(int x,int p=-1)
{
	vis[x]=1;
	sz[x]=1;
	for(auto y:ma[x])
	{
		if(!vis[y])
		{
			dfs_sz(y,x);
			sz[x]+=sz[y];
		}
	}
}
bool asd=0;
void take(int x,int cnt,bool sp)
{
	vis[x]=1;
	if(sp)
	{
		if(two.size()<cnt)
		{
			two.insert(x);
		}
	}
	else
	{
		if(one.size()<cnt)
		{
			one.insert(x);
		}
	}
	for(auto y:ma[x])
	{
		if(!vis[y])
		{
			take(y,cnt,sp);
		}
	}
}
void find_edge(int x,int a,int b,int p=-1)
{
	vis[x]=1;
	if(asd)
		return;
	for(auto y:ma[x])
	{
		if(!vis[y])
		{
			if(asd)
			{
				return;
			}
			if(sz[y]>=b and (n-sz[y])>=a)
			{
				one.clear();
				two.clear();
				for(int i=1;i<=n;i++)
					vis[i]=0;
				vis[x]=1;
				take(y,b,1);
				for(int i=1;i<=n;i++)
					vis[i]=0;
				vis[y]=1;
				take(x,a,0);
				asd=1;
				return;
			}
			if(sz[y]>=a and (n-sz[y])>=b)
			{
				one.clear();
				two.clear();
				for(int i=1;i<=n;i++)
					vis[i]=0;
				vis[x]=1;
				take(y,a,0);
				for(int i=1;i<=n;i++)
					vis[i]=0;
				vis[y]=1;
				take(x,b,1);
				asd=1;
				return;
			}
			sz[x]-=sz[y];
			sz[y]+=sz[x];
			find_edge(y,a,b,x);
			sz[y]-=sz[x];
			sz[x]+=sz[y];
		}
	}
}
void dfs(int x,int a,int b)
{
	if(one.size()<a)
	{
		one.insert(x);
	}
	else if(two.size()<b)
	{
		two.insert(x);
	}
	vis[x]=1;
	for(auto y:ma[x])
	{
		if(!vis[y])
		{
			dfs(y,a,b);
		}
	}
}
vector<int> find_split(int n1, int a, int b, int c, vector<int> p, vector<int> q)
{
	n=n1;
	// Swap a,b,c to make a<=b<=c hold and assign new color to each
	vector<pair<int,int>> aps;
	aps.push_back({a,1});
	aps.push_back({b,2});
	aps.push_back({c,3});
	sort(begin(aps),end(aps));
	int colora,colorb,colorc;
	a=aps[0].first;
	colora=aps[0].second;
	b=aps[1].first;
	colorb=aps[1].second;
	c=aps[2].first;
	colorc=aps[2].second;
	// Sorting done
	// Adding Edges
	int m=p.size();
	int mx=0;
	for(int j=0;j<m;j++)
	{
		p[j]++;
		q[j]++;
		ma[p[j]].push_back(q[j]);
		ma[q[j]].push_back(p[j]);
		in[p[j]]++;
		in[q[j]]++;
		mx=max(mx,in[p[j]]);
		mx=max(mx,in[q[j]]);
	}
	// Edges added
	// if(m==(n-1))
	// {
		// Simple as eating ice cream
		// Find an edge such that if remove it then the two component have size1,size2
		// size1>=size2
		// size1>=a and size2>=b
		// then we can make answer
		dfs_sz(1);
		for(int i=1;i<=n;i++)
		{
			vis[i]=0;
		}
		find_edge(1,a,b);
		for(int i=1;i<=n;i++)
		{
			color[i]=colorc;
		}
		for(auto i:one)
		{
			color[i]=colora;
		}
		for(auto i:two)
		{
			color[i]=colorb;
		}
		vector<int> ans;
		for(int i=1;i<=n;i++)
		{
			if(!asd)
			{
				ans.push_back(0);
			}
			else
				ans.push_back(color[i]);
		}
		return ans;
	// }
	if(a==1 or mx<=2)
	{
		bool pos=1;
		for(int j=1;j<=n;j++)
		{
			if(ma[j].size()==1)
			{
				dfs(j,a,b);
				pos=0;
				break;
			}
		}
		if(pos)
		{
			dfs(1,a,b);
		}
		for(int i=1;i<=n;i++)
		{
			color[i]=colorc;
		}
		for(auto i:two)
		{
			color[i]=colorb;
		}
		for(auto i:one)
		{
			color[i]=colora;
		}
		vector<int> ans;
		for(int i=1;i<=n;i++)
		{
			ans.push_back(color[i]);
		}
		return ans;
	}
	// exit(-1);
	return {};
}

Compilation message

split.cpp: In function 'void take(int, int, bool)':
split.cpp:30:16: warning: comparison of integer expressions of different signedness: 'std::set<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   30 |   if(two.size()<cnt)
      |      ~~~~~~~~~~^~~~
split.cpp:37:16: warning: comparison of integer expressions of different signedness: 'std::set<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   37 |   if(one.size()<cnt)
      |      ~~~~~~~~~~^~~~
split.cpp: In function 'void dfs(int, int, int)':
split.cpp:103:15: warning: comparison of integer expressions of different signedness: 'std::set<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  103 |  if(one.size()<a)
      |     ~~~~~~~~~~^~
split.cpp:107:20: warning: comparison of integer expressions of different signedness: 'std::set<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  107 |  else if(two.size()<b)
      |          ~~~~~~~~~~^~

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6492 KB ok, correct split
2 Correct 2 ms 6492 KB ok, correct split
3 Correct 1 ms 6492 KB ok, correct split
4 Correct 1 ms 6488 KB ok, correct split
5 Correct 1 ms 6660 KB ok, correct split
6 Correct 1 ms 6492 KB ok, correct split
7 Correct 65 ms 22896 KB ok, correct split
8 Correct 43 ms 17632 KB ok, correct split
9 Correct 56 ms 19148 KB ok, correct split
10 Correct 52 ms 20184 KB ok, correct split
11 Correct 80 ms 26248 KB ok, correct split

Subtask #2
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6488 KB ok, correct split
2 Correct 1 ms 6492 KB ok, correct split
3 Correct 2 ms 6492 KB ok, correct split
4 Correct 56 ms 17132 KB ok, correct split
5 Correct 49 ms 14808 KB ok, correct split
6 Correct 54 ms 20180 KB ok, correct split
7 Correct 55 ms 19660 KB ok, correct split
8 Correct 97 ms 16220 KB ok, correct split
9 Correct 57 ms 14548 KB ok, correct split
10 Correct 44 ms 15336 KB ok, correct split
11 Correct 49 ms 15460 KB ok, correct split
12 Correct 41 ms 15312 KB ok, correct split

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6492 KB ok, correct split
2 Correct 61 ms 15308 KB ok, correct split
3 Correct 16 ms 9048 KB ok, correct split
4 Correct 1 ms 6492 KB ok, correct split
5 Correct 66 ms 18184 KB ok, correct split
6 Correct 62 ms 17880 KB ok, correct split
7 Correct 59 ms 18580 KB ok, correct split
8 Correct 87 ms 19096 KB ok, correct split
9 Correct 59 ms 18388 KB ok, correct split
10 Correct 14 ms 8792 KB ok, no valid answer
11 Correct 19 ms 9560 KB ok, no valid answer
12 Correct 35 ms 12760 KB ok, no valid answer
13 Correct 38 ms 12504 KB ok, no valid answer
14 Correct 31 ms 13000 KB ok, no valid answer

Subtask #4
0 / 24.0

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

Subtask #5
0 / 36.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6492 KB ok, correct split
2 Correct 2 ms 6492 KB ok, correct split
3 Correct 1 ms 6492 KB ok, correct split
4 Correct 1 ms 6488 KB ok, correct split
5 Correct 1 ms 6660 KB ok, correct split
6 Correct 1 ms 6492 KB ok, correct split
7 Correct 65 ms 22896 KB ok, correct split
8 Correct 43 ms 17632 KB ok, correct split
9 Correct 56 ms 19148 KB ok, correct split
10 Correct 52 ms 20184 KB ok, correct split
11 Correct 80 ms 26248 KB ok, correct split
12 Correct 1 ms 6488 KB ok, correct split
13 Correct 1 ms 6492 KB ok, correct split
14 Correct 2 ms 6492 KB ok, correct split
15 Correct 56 ms 17132 KB ok, correct split
16 Correct 49 ms 14808 KB ok, correct split
17 Correct 54 ms 20180 KB ok, correct split
18 Correct 55 ms 19660 KB ok, correct split
19 Correct 97 ms 16220 KB ok, correct split
20 Correct 57 ms 14548 KB ok, correct split
21 Correct 44 ms 15336 KB ok, correct split
22 Correct 49 ms 15460 KB ok, correct split
23 Correct 41 ms 15312 KB ok, correct split
24 Correct 1 ms 6492 KB ok, correct split
25 Correct 61 ms 15308 KB ok, correct split
26 Correct 16 ms 9048 KB ok, correct split
27 Correct 1 ms 6492 KB ok, correct split
28 Correct 66 ms 18184 KB ok, correct split
29 Correct 62 ms 17880 KB ok, correct split
30 Correct 59 ms 18580 KB ok, correct split
31 Correct 87 ms 19096 KB ok, correct split
32 Correct 59 ms 18388 KB ok, correct split
33 Correct 14 ms 8792 KB ok, no valid answer
34 Correct 19 ms 9560 KB ok, no valid answer
35 Correct 35 ms 12760 KB ok, no valid answer
36 Correct 38 ms 12504 KB ok, no valid answer
37 Correct 31 ms 13000 KB ok, no valid answer
38 Correct 1 ms 6492 KB ok, correct split
39 Correct 1 ms 6492 KB ok, no valid answer
40 Correct 1 ms 6492 KB ok, correct split
41 Correct 1 ms 6492 KB ok, correct split
42 Incorrect 1 ms 6492 KB invalid split: #1=9, #2=3, #3=4
43 Halted 0 ms 0 KB -