oj.uz

Submission #891507

# Submission time Handle Problem Language Result Execution time Memory
891507 2023-12-23T06:31:13 Z Faisal_Saqib Split the Attractions (IOI19_split) C++17
40 / 100
 74 ms 23096 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)
{
	sz[x]=1;
	for(auto y:ma[x])
	{
		if(y!=p)
		{
			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);
		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:29:16: warning: comparison of integer expressions of different signedness: 'std::set<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   29 |   if(two.size()<cnt)
      |      ~~~~~~~~~~^~~~
split.cpp:36:16: warning: comparison of integer expressions of different signedness: 'std::set<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   36 |   if(one.size()<cnt)
      |      ~~~~~~~~~~^~~~
split.cpp: In function 'void dfs(int, int, int)':
split.cpp:102:15: warning: comparison of integer expressions of different signedness: 'std::set<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  102 |  if(one.size()<a)
      |     ~~~~~~~~~~^~
split.cpp:106:20: warning: comparison of integer expressions of different signedness: 'std::set<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  106 |  else if(two.size()<b)
      |          ~~~~~~~~~~^~

Subtask #1
7.0 / 7.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 1 ms 6492 KB ok, correct split
4 Correct 1 ms 6492 KB ok, correct split
5 Correct 1 ms 6492 KB ok, correct split
6 Correct 1 ms 6492 KB ok, correct split
7 Correct 62 ms 23096 KB ok, correct split
8 Correct 50 ms 17624 KB ok, correct split
9 Correct 74 ms 19152 KB ok, correct split
10 Correct 40 ms 16600 KB ok, correct split
11 Correct 60 ms 19788 KB ok, correct split

Subtask #2
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6492 KB ok, correct split
2 Correct 1 ms 6492 KB ok, correct split
3 Correct 1 ms 6492 KB ok, correct split
4 Correct 52 ms 15392 KB ok, correct split
5 Correct 51 ms 14796 KB ok, correct split
6 Correct 39 ms 16604 KB ok, correct split
7 Correct 60 ms 19756 KB ok, correct split
8 Correct 73 ms 15916 KB ok, correct split
9 Correct 47 ms 14228 KB ok, correct split
10 Correct 46 ms 15560 KB ok, correct split
11 Correct 42 ms 15248 KB ok, correct split
12 Correct 43 ms 15248 KB ok, correct split

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6488 KB ok, correct split
2 Correct 53 ms 15456 KB ok, correct split
3 Correct 16 ms 9488 KB ok, correct split
4 Correct 1 ms 6492 KB ok, correct split
5 Correct 59 ms 19096 KB ok, correct split
6 Correct 71 ms 19160 KB ok, correct split
7 Correct 60 ms 19836 KB ok, correct split
8 Correct 60 ms 20056 KB ok, correct split
9 Correct 57 ms 19668 KB ok, correct split
10 Correct 14 ms 9048 KB ok, no valid answer
11 Correct 20 ms 10200 KB ok, no valid answer
12 Correct 36 ms 14040 KB ok, no valid answer
13 Correct 39 ms 13788 KB ok, no valid answer
14 Correct 32 ms 14076 KB ok, no valid answer

Subtask #4
0 / 24.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 6488 KB WA in grader: Invalid length of the result.
2 Halted 0 ms 0 KB -

Subtask #5
0 / 36.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 1 ms 6492 KB ok, correct split
4 Correct 1 ms 6492 KB ok, correct split
5 Correct 1 ms 6492 KB ok, correct split
6 Correct 1 ms 6492 KB ok, correct split
7 Correct 62 ms 23096 KB ok, correct split
8 Correct 50 ms 17624 KB ok, correct split
9 Correct 74 ms 19152 KB ok, correct split
10 Correct 40 ms 16600 KB ok, correct split
11 Correct 60 ms 19788 KB ok, correct split
12 Correct 1 ms 6492 KB ok, correct split
13 Correct 1 ms 6492 KB ok, correct split
14 Correct 1 ms 6492 KB ok, correct split
15 Correct 52 ms 15392 KB ok, correct split
16 Correct 51 ms 14796 KB ok, correct split
17 Correct 39 ms 16604 KB ok, correct split
18 Correct 60 ms 19756 KB ok, correct split
19 Correct 73 ms 15916 KB ok, correct split
20 Correct 47 ms 14228 KB ok, correct split
21 Correct 46 ms 15560 KB ok, correct split
22 Correct 42 ms 15248 KB ok, correct split
23 Correct 43 ms 15248 KB ok, correct split
24 Correct 1 ms 6488 KB ok, correct split
25 Correct 53 ms 15456 KB ok, correct split
26 Correct 16 ms 9488 KB ok, correct split
27 Correct 1 ms 6492 KB ok, correct split
28 Correct 59 ms 19096 KB ok, correct split
29 Correct 71 ms 19160 KB ok, correct split
30 Correct 60 ms 19836 KB ok, correct split
31 Correct 60 ms 20056 KB ok, correct split
32 Correct 57 ms 19668 KB ok, correct split
33 Correct 14 ms 9048 KB ok, no valid answer
34 Correct 20 ms 10200 KB ok, no valid answer
35 Correct 36 ms 14040 KB ok, no valid answer
36 Correct 39 ms 13788 KB ok, no valid answer
37 Correct 32 ms 14076 KB ok, no valid answer
38 Incorrect 1 ms 6488 KB WA in grader: Invalid length of the result.
39 Halted 0 ms 0 KB -