oj.uz

Submission #893352

# Submission time Handle Problem Language Result Execution time Memory
893352 2023-12-27T03:08:37 Z Faisal_Saqib Split the Attractions (IOI19_split) C++17
18 / 100
 2000 ms 26320 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)
			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 5724 KB ok, correct split
2 Correct 2 ms 5724 KB ok, correct split
3 Correct 2 ms 5724 KB ok, correct split
4 Correct 2 ms 5880 KB ok, correct split
5 Correct 2 ms 5720 KB ok, correct split
6 Correct 2 ms 5724 KB ok, correct split
7 Correct 93 ms 23452 KB ok, correct split
8 Correct 53 ms 18132 KB ok, correct split
9 Correct 75 ms 19672 KB ok, correct split
10 Correct 82 ms 20692 KB ok, correct split
11 Correct 109 ms 26320 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 2 ms 5724 KB ok, correct split
3 Correct 2 ms 5724 KB ok, correct split
4 Correct 63 ms 17916 KB ok, correct split
5 Correct 63 ms 15228 KB ok, correct split
6 Correct 72 ms 20696 KB ok, correct split
7 Correct 71 ms 20172 KB ok, correct split
8 Correct 78 ms 17620 KB ok, correct split
9 Correct 57 ms 15052 KB ok, correct split
10 Correct 44 ms 15492 KB ok, correct split
11 Correct 53 ms 15220 KB ok, correct split
12 Correct 48 ms 15572 KB ok, correct split

Subtask #3
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 5720 KB ok, correct split
2 Correct 78 ms 15568 KB ok, correct split
3 Correct 16 ms 8796 KB ok, correct split
4 Correct 2 ms 5724 KB ok, correct split
5 Correct 60 ms 18524 KB ok, correct split
6 Correct 59 ms 18536 KB ok, correct split
7 Correct 78 ms 18900 KB ok, correct split
8 Correct 87 ms 19324 KB ok, correct split
9 Correct 79 ms 18692 KB ok, correct split
10 Execution timed out 2052 ms 8984 KB Time limit exceeded
11 Halted 0 ms 0 KB -

Subtask #4
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 5724 KB ok, correct split
2 Correct 2 ms 5720 KB ok, no valid answer
3 Correct 1 ms 5724 KB ok, correct split
4 Correct 2 ms 5724 KB ok, correct split
5 Incorrect 2 ms 5724 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 5724 KB ok, correct split
2 Correct 2 ms 5724 KB ok, correct split
3 Correct 2 ms 5724 KB ok, correct split
4 Correct 2 ms 5880 KB ok, correct split
5 Correct 2 ms 5720 KB ok, correct split
6 Correct 2 ms 5724 KB ok, correct split
7 Correct 93 ms 23452 KB ok, correct split
8 Correct 53 ms 18132 KB ok, correct split
9 Correct 75 ms 19672 KB ok, correct split
10 Correct 82 ms 20692 KB ok, correct split
11 Correct 109 ms 26320 KB ok, correct split
12 Correct 2 ms 5720 KB ok, correct split
13 Correct 2 ms 5724 KB ok, correct split
14 Correct 2 ms 5724 KB ok, correct split
15 Correct 63 ms 17916 KB ok, correct split
16 Correct 63 ms 15228 KB ok, correct split
17 Correct 72 ms 20696 KB ok, correct split
18 Correct 71 ms 20172 KB ok, correct split
19 Correct 78 ms 17620 KB ok, correct split
20 Correct 57 ms 15052 KB ok, correct split
21 Correct 44 ms 15492 KB ok, correct split
22 Correct 53 ms 15220 KB ok, correct split
23 Correct 48 ms 15572 KB ok, correct split
24 Correct 2 ms 5720 KB ok, correct split
25 Correct 78 ms 15568 KB ok, correct split
26 Correct 16 ms 8796 KB ok, correct split
27 Correct 2 ms 5724 KB ok, correct split
28 Correct 60 ms 18524 KB ok, correct split
29 Correct 59 ms 18536 KB ok, correct split
30 Correct 78 ms 18900 KB ok, correct split
31 Correct 87 ms 19324 KB ok, correct split
32 Correct 79 ms 18692 KB ok, correct split
33 Execution timed out 2052 ms 8984 KB Time limit exceeded
34 Halted 0 ms 0 KB -