oj.uz

Submission #891502

# Submission time Handle Problem Language Result Execution time Memory
891502 2023-12-23T06:14:22 Z Faisal_Saqib Split the Attractions (IOI19_split) C++17
18 / 100
 74 ms 22252 KB 
#include <vector>
#include <set>
#include <algorithm>
using namespace std;
const int N=2e5+1;
vector<int> ma[N];
int color[N],in[N];
bool vis[N];
set<int> one,two;
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 n, int a, int b, int c, vector<int> p, vector<int> q)
{
	// 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(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;
	}
	else
	{
		// Greedy algorithm 
		// Find Set A 
		// Then Try to Find Set b in every component
	}
	// exit(-1);
	// return {};
}

Compilation message

split.cpp: In function 'void dfs(int, int, int)':
split.cpp:12:15: warning: comparison of integer expressions of different signedness: 'std::set<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   12 |  if(one.size()<a)
      |     ~~~~~~~~~~^~
split.cpp:16:20: warning: comparison of integer expressions of different signedness: 'std::set<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   16 |  else if(two.size()<b)
      |          ~~~~~~~~~~^~
split.cpp: In function 'std::vector<int> find_split(int, int, int, int, std::vector<int>, std::vector<int>)':
split.cpp:32:24: warning: control reaches end of non-void function [-Wreturn-type]
   32 |  vector<pair<int,int>> aps;
      |                        ^~~

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 5724 KB ok, correct split
2 Correct 1 ms 5724 KB ok, correct split
3 Correct 1 ms 5724 KB ok, correct split
4 Correct 2 ms 5724 KB ok, correct split
5 Correct 2 ms 5724 KB ok, correct split
6 Correct 2 ms 5972 KB ok, correct split
7 Correct 60 ms 22252 KB ok, correct split
8 Correct 42 ms 19168 KB ok, correct split
9 Correct 74 ms 21460 KB ok, correct split
10 Correct 43 ms 18900 KB ok, correct split
11 Correct 70 ms 22248 KB ok, correct split

Subtask #2
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 5724 KB ok, correct split
2 Correct 2 ms 5720 KB ok, correct split
3 Correct 1 ms 5720 KB ok, correct split
4 Correct 53 ms 17400 KB ok, correct split
5 Correct 49 ms 15312 KB ok, correct split
6 Correct 43 ms 18900 KB ok, correct split
7 Correct 55 ms 21456 KB ok, correct split
8 Correct 68 ms 17616 KB ok, correct split
9 Correct 47 ms 14796 KB ok, correct split
10 Correct 42 ms 15316 KB ok, correct split
11 Correct 44 ms 15304 KB ok, correct split
12 Correct 46 ms 15600 KB ok, correct split

Subtask #3
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 5724 KB ok, correct split
2 Runtime error 32 ms 22104 KB Execution killed with signal 6
3 Halted 0 ms 0 KB -

Subtask #4
0 / 24.0

# Verdict Execution time Memory Grader output
1 Runtime error 6 ms 11352 KB Execution killed with signal 6
2 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 1 ms 5724 KB ok, correct split
3 Correct 1 ms 5724 KB ok, correct split
4 Correct 2 ms 5724 KB ok, correct split
5 Correct 2 ms 5724 KB ok, correct split
6 Correct 2 ms 5972 KB ok, correct split
7 Correct 60 ms 22252 KB ok, correct split
8 Correct 42 ms 19168 KB ok, correct split
9 Correct 74 ms 21460 KB ok, correct split
10 Correct 43 ms 18900 KB ok, correct split
11 Correct 70 ms 22248 KB ok, correct split
12 Correct 2 ms 5724 KB ok, correct split
13 Correct 2 ms 5720 KB ok, correct split
14 Correct 1 ms 5720 KB ok, correct split
15 Correct 53 ms 17400 KB ok, correct split
16 Correct 49 ms 15312 KB ok, correct split
17 Correct 43 ms 18900 KB ok, correct split
18 Correct 55 ms 21456 KB ok, correct split
19 Correct 68 ms 17616 KB ok, correct split
20 Correct 47 ms 14796 KB ok, correct split
21 Correct 42 ms 15316 KB ok, correct split
22 Correct 44 ms 15304 KB ok, correct split
23 Correct 46 ms 15600 KB ok, correct split
24 Correct 2 ms 5724 KB ok, correct split
25 Runtime error 32 ms 22104 KB Execution killed with signal 6
26 Halted 0 ms 0 KB -