oj.uz

Submission #893355

# Submission time Handle Problem Language Result Execution time Memory
893355 2023-12-27T03:10:06 Z Faisal_Saqib Split the Attractions (IOI19_split) C++17
40 / 100
 85 ms 25196 KB 
#include <vector>
#include <set>
#include <algorithm>
using namespace std;
const int N=2e5+1;
vector<int> ma[N];
int color[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;
	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;
	int m=p.size();
	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]);
	}
	for(int ver=1;ver<=n;ver++)
	{
		one.clear();
		two.clear();
		asd=0;
		dfs_sz(ver);
		for(int i=1;i<=n;i++)
			vis[i]=0;
		find_edge(ver,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]);
		}
		if(asd or (m==(n-1)) or a==1)
			return ans;
	}
	return vector<int>(n,0);
}

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:101:15: warning: comparison of integer expressions of different signedness: 'std::set<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  101 |  if(one.size()<a)
      |     ~~~~~~~~~~^~
split.cpp:105:20: warning: comparison of integer expressions of different signedness: 'std::set<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  105 |  else if(two.size()<b)
      |          ~~~~~~~~~~^~

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 5720 KB ok, correct split
2 Correct 1 ms 5724 KB ok, correct split
3 Correct 1 ms 5724 KB ok, correct split
4 Correct 1 ms 5704 KB ok, correct split
5 Correct 2 ms 5724 KB ok, correct split
6 Correct 1 ms 5724 KB ok, correct split
7 Correct 63 ms 22220 KB ok, correct split
8 Correct 45 ms 16856 KB ok, correct split
9 Correct 58 ms 18384 KB ok, correct split
10 Correct 49 ms 19528 KB ok, correct split
11 Correct 71 ms 25196 KB ok, correct split

Subtask #2
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 5720 KB ok, correct split
2 Correct 1 ms 5720 KB ok, correct split
3 Correct 1 ms 5724 KB ok, correct split
4 Correct 54 ms 16336 KB ok, correct split
5 Correct 51 ms 14032 KB ok, correct split
6 Correct 52 ms 19412 KB ok, correct split
7 Correct 57 ms 18988 KB ok, correct split
8 Correct 85 ms 15568 KB ok, correct split
9 Correct 59 ms 13764 KB ok, correct split
10 Correct 43 ms 14536 KB ok, correct split
11 Correct 41 ms 14536 KB ok, correct split
12 Correct 45 ms 14536 KB ok, correct split

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 5720 KB ok, correct split
2 Correct 52 ms 14548 KB ok, correct split
3 Correct 16 ms 8284 KB ok, correct split
4 Correct 1 ms 5920 KB ok, correct split
5 Correct 57 ms 17368 KB ok, correct split
6 Correct 57 ms 17112 KB ok, correct split
7 Correct 63 ms 17804 KB ok, correct split
8 Correct 64 ms 18300 KB ok, correct split
9 Correct 59 ms 17620 KB ok, correct split
10 Correct 17 ms 8024 KB ok, no valid answer
11 Correct 20 ms 9420 KB ok, no valid answer
12 Correct 36 ms 13080 KB ok, no valid answer
13 Correct 39 ms 13012 KB ok, no valid answer
14 Correct 33 ms 13256 KB ok, no valid answer

Subtask #4
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 5720 KB ok, correct split
2 Correct 1 ms 5720 KB ok, no valid answer
3 Correct 1 ms 5724 KB ok, correct split
4 Correct 1 ms 5724 KB ok, correct split
5 Incorrect 2 ms 5812 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 2 ms 5720 KB ok, correct split
2 Correct 1 ms 5724 KB ok, correct split
3 Correct 1 ms 5724 KB ok, correct split
4 Correct 1 ms 5704 KB ok, correct split
5 Correct 2 ms 5724 KB ok, correct split
6 Correct 1 ms 5724 KB ok, correct split
7 Correct 63 ms 22220 KB ok, correct split
8 Correct 45 ms 16856 KB ok, correct split
9 Correct 58 ms 18384 KB ok, correct split
10 Correct 49 ms 19528 KB ok, correct split
11 Correct 71 ms 25196 KB ok, correct split
12 Correct 2 ms 5720 KB ok, correct split
13 Correct 1 ms 5720 KB ok, correct split
14 Correct 1 ms 5724 KB ok, correct split
15 Correct 54 ms 16336 KB ok, correct split
16 Correct 51 ms 14032 KB ok, correct split
17 Correct 52 ms 19412 KB ok, correct split
18 Correct 57 ms 18988 KB ok, correct split
19 Correct 85 ms 15568 KB ok, correct split
20 Correct 59 ms 13764 KB ok, correct split
21 Correct 43 ms 14536 KB ok, correct split
22 Correct 41 ms 14536 KB ok, correct split
23 Correct 45 ms 14536 KB ok, correct split
24 Correct 2 ms 5720 KB ok, correct split
25 Correct 52 ms 14548 KB ok, correct split
26 Correct 16 ms 8284 KB ok, correct split
27 Correct 1 ms 5920 KB ok, correct split
28 Correct 57 ms 17368 KB ok, correct split
29 Correct 57 ms 17112 KB ok, correct split
30 Correct 63 ms 17804 KB ok, correct split
31 Correct 64 ms 18300 KB ok, correct split
32 Correct 59 ms 17620 KB ok, correct split
33 Correct 17 ms 8024 KB ok, no valid answer
34 Correct 20 ms 9420 KB ok, no valid answer
35 Correct 36 ms 13080 KB ok, no valid answer
36 Correct 39 ms 13012 KB ok, no valid answer
37 Correct 33 ms 13256 KB ok, no valid answer
38 Correct 2 ms 5720 KB ok, correct split
39 Correct 1 ms 5720 KB ok, no valid answer
40 Correct 1 ms 5724 KB ok, correct split
41 Correct 1 ms 5724 KB ok, correct split
42 Incorrect 2 ms 5812 KB invalid split: #1=9, #2=3, #3=4
43 Halted 0 ms 0 KB -