oj.uz

Submission #891475

# Submission time Handle Problem Language Result Execution time Memory
891475 2023-12-23T05:25:35 Z UmairAhmadMirza Split the Attractions (IOI19_split) C++17
18 / 100
 55 ms 16496 KB 
#include <bits/stdc++.h>
using namespace std;
int const N=1e5+5;
vector<int> adj[N];
int col[N];
bool vis[N];
int cnt=0;
int aa=0,bb=0,cc=0;
int col_seq[3]={1,2,3};
int sz[N];
void dfs(int node){
	if(cnt==bb)
		return;
	vis[node]=1;
	col[node]=2;
	cnt++;
	for(auto i:adj[node])
		if(!vis[i])
			dfs(i);
}
void dfs1(int node){
	if(cnt==aa || col[node]!=3)
		return;
	vis[node]=1;
	col[node]=1;
	cnt++;
	for(auto i:adj[node])
		if(!vis[i])
			dfs1(i);
}
void fill_all(int node,int par){
	if(cnt<=0)
		return;
	col[node]=col_seq[0];
	cnt--;
	for(auto i:adj[node])
		if(i!=par)
			fill_all(i,node);
}
int mini=N;
int found=-1;
int par_found=0;
void sub(int node,int par){
	sz[node]=1;
	for(auto i:adj[node])
		if(i!=par){
			sub(i,node);
			sz[node]+=sz[i];
		}
	if(sz[node]>=aa && sz[node]<mini){
		mini=sz[node];
		found=node;
		par_found=par;
	}
}
bool free_vis[N];
int cnt_free(int node,int par){
	if(col[node]==col_seq[0])
		return 0;
	int c=1;
	free_vis[node]=1;
	for(auto i:adj[node])
		if(i!=par)
			c+=cnt_free(i,node);
	return c;
}
void fill_it(int node,int par){
	if(cnt<=0)
		return;
	if(col[node]==col_seq[0])
		return;
	col[node]=col_seq[1];
	cnt--;
	for(auto i:adj[node])
		if(i!=par)
			fill_it(i,node);
}
vector<int> find_split(int n, int a, int b, int c, vector<int> p, vector<int> q){
	int m=p.size();
	for (int i = 0; i < m; ++i)
	{
		adj[p[i]].push_back(q[i]);
		adj[q[i]].push_back(p[i]);
	}
	aa=a;
	bb=b;
	cc=c;
	for (int i = 0; i < n; ++i)
		col[i]=3;
	vector<int> ans;
	if(a==1){
		dfs(0);
		for (int i = 0; i < n; ++i)
			if(col[i]==3){
				col[i]=1;
				break;
			}
	}
	else if(m==n-1){
		if(aa>bb){
			swap(aa,bb);
			swap(col_seq[0],col_seq[1]);
		}
		if(cc<bb){
			swap(cc,bb);
			swap(col_seq[1],col_seq[2]);
		}
		if(aa>bb){
			swap(aa,bb);
			swap(col_seq[0],col_seq[1]);
		}
		for (int i = 0; i < n; ++i)
			col[i]=col_seq[2];
		cnt=aa;
		sub(0,-1);
		fill_all(found,par_found);
		bool done=0;
		for (int i = 0; i < n; ++i)
			if(free_vis[i]==0 && cnt_free(i,-1)>=bb){
				cnt=bb;
				fill_it(i,-1);
				done=1;
			}
		if(done==0){
			for (int i = 0; i < n; ++i)
				ans.push_back(0);
			return ans;
		}
	}
	else{
		int u=0;
		for (int i = 0; i < n; ++i)
			if(adj[i].size()==1)
				u=i;
		dfs(u);
		for (int i = 0; i < n; ++i)
			if(vis[i]==0)
				u=i;
		cnt=0;
		dfs1(u);
	}
	for (int i = 0; i < n; ++i)
		ans.push_back(col[i]);
	return ans;
}

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 3420 KB ok, correct split
2 Correct 1 ms 3420 KB ok, correct split
3 Correct 1 ms 3420 KB ok, correct split
4 Correct 1 ms 3420 KB ok, correct split
5 Correct 1 ms 3420 KB ok, correct split
6 Correct 1 ms 3420 KB ok, correct split
7 Correct 53 ms 16496 KB ok, correct split
8 Correct 38 ms 10976 KB ok, correct split
9 Correct 50 ms 13528 KB ok, correct split
10 Correct 35 ms 8928 KB ok, correct split
11 Correct 36 ms 9944 KB ok, correct split

Subtask #2
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 3420 KB ok, correct split
2 Correct 1 ms 3420 KB ok, correct split
3 Correct 1 ms 3416 KB ok, correct split
4 Correct 45 ms 9948 KB ok, correct split
5 Correct 35 ms 8920 KB ok, correct split
6 Correct 34 ms 8924 KB ok, correct split
7 Correct 41 ms 10464 KB ok, correct split
8 Correct 55 ms 11224 KB ok, correct split
9 Correct 35 ms 8928 KB ok, correct split
10 Correct 35 ms 9472 KB ok, correct split
11 Correct 31 ms 9428 KB ok, correct split
12 Correct 31 ms 9424 KB ok, correct split

Subtask #3
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 3416 KB ok, correct split
2 Incorrect 41 ms 9172 KB jury found a solution, contestant did not
3 Halted 0 ms 0 KB -

Subtask #4
0 / 24.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 3420 KB invalid split: #1=3, #2=2, #3=4
2 Halted 0 ms 0 KB -

Subtask #5
0 / 36.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 3420 KB ok, correct split
2 Correct 1 ms 3420 KB ok, correct split
3 Correct 1 ms 3420 KB ok, correct split
4 Correct 1 ms 3420 KB ok, correct split
5 Correct 1 ms 3420 KB ok, correct split
6 Correct 1 ms 3420 KB ok, correct split
7 Correct 53 ms 16496 KB ok, correct split
8 Correct 38 ms 10976 KB ok, correct split
9 Correct 50 ms 13528 KB ok, correct split
10 Correct 35 ms 8928 KB ok, correct split
11 Correct 36 ms 9944 KB ok, correct split
12 Correct 1 ms 3420 KB ok, correct split
13 Correct 1 ms 3420 KB ok, correct split
14 Correct 1 ms 3416 KB ok, correct split
15 Correct 45 ms 9948 KB ok, correct split
16 Correct 35 ms 8920 KB ok, correct split
17 Correct 34 ms 8924 KB ok, correct split
18 Correct 41 ms 10464 KB ok, correct split
19 Correct 55 ms 11224 KB ok, correct split
20 Correct 35 ms 8928 KB ok, correct split
21 Correct 35 ms 9472 KB ok, correct split
22 Correct 31 ms 9428 KB ok, correct split
23 Correct 31 ms 9424 KB ok, correct split
24 Correct 1 ms 3416 KB ok, correct split
25 Incorrect 41 ms 9172 KB jury found a solution, contestant did not
26 Halted 0 ms 0 KB -