oj.uz

Submission #893559

# Submission time Handle Problem Language Result Execution time Memory
893559 2023-12-27T07:03:01 Z Faisal_Saqib Split the Attractions (IOI19_split) C++17
11 / 100
 69 ms 29024 KB 
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
const int N=1e5+2;
vector<int> ma[N],ch[N],ans;
bool vis[N];
int sz[N],up[N],h[N],n;
pair<int,int> comp[3];
bool f=0;
void dfs_color1(int x,int co)
{
	if(comp[co].first==0)
		return;
	vis[x]=1;
	ans[x]=comp[co].second;
	comp[co].first--;
	for(int i:ma[x])
		if(!vis[i])
			dfs_color1(i,co);
}
void dfs_color(int x,int co)
{
	if(comp[co].first==0)
		return;
	vis[x]=1;
	ans[x]=comp[co].second;
	comp[co].first--;
	for(int i:ch[x])
		if(!vis[i])
			dfs_color(i,co);
}
void dfs_ch(int x)
{
	sz[x]=1;
	vis[x]=1;
	up[x]=h[x];
	for(int y:ma[x])
	{
		if(!vis[y])
		{
			h[y]=h[x]+1;
			dfs_ch(y);
			sz[x]+=sz[y];
			ch[x].push_back(y);
			up[x]=min(up[x],up[y]);
		}
		else
		{
			up[x]=min(up[x],h[y]);
		}
	}
}
void dfs(int x,int q=-1)
{
	if(f)
		return;
	int P1=sz[x];
	int P2=sz[0]-P1;
	for(int y:ch[x])
	{
		dfs(y);
		if(f)
			return;
	}
	vector<int> left;
	for(int y:ch[x])
	{
		if(up[y]<h[x] and (P1-sz[y])>=comp[0].first)
		{
			P1-=sz[y];
			P2+=sz[y];
		}
		else
			left.push_back(y);
	}
	if(P1>=comp[0].first and P2>=comp[1].first)
	{
		for(int i=0;i<n;i++)
			vis[i]=0;
		vis[x]=1;
		ans[x]=comp[0].second;
		comp[0].first--;
		for(int y:left)
			dfs_color(y,0);
		dfs_color1(1,1);
		f=1;
		return;
	}
	if(P2>=comp[0].first and P1>=comp[1].first)
	{
		for(int i=0;i<n;i++)
			vis[i]=0;
		vis[x]=1;
		ans[x]=comp[1].second;
		comp[1].first--;
		for(int y:left)
			dfs_color(y,1);
		dfs_color1(1,0);
		f=1;
		return;
	}
}
vector<int> find_split(int n1, int a, int b, int c, vector<int> p, vector<int> q)
{
	n=n1;
	comp[0]={a,1},comp[1]={b,2},comp[2]={c,3};
	sort(comp,comp+3);
	int m=p.size();
	for(int i=0;i<m;i++)
		ma[p[i]].push_back(q[i]),ma[q[i]].push_back(p[i]);
	ans.resize(n,comp[2].second);
	for(int j=0;j<1;j++)
	{
		dfs_ch(j);
		for(int i=0;i<n;i++)
		{
			ans[i]=comp[2].second;;
			vis[i]=0;
		}
		dfs(j);
		if(f)
			return ans;	
	}
	if(!f)
		for(int i=0;i<n;i++)
			ans[i]=0;
	return ans;
}

Subtask #1
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 5976 KB ok, correct split
2 Correct 2 ms 6232 KB ok, correct split
3 Correct 2 ms 6236 KB ok, correct split
4 Incorrect 2 ms 6236 KB invalid split: #1=3, #2=0, #3=1
5 Halted 0 ms 0 KB -

Subtask #2
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 6236 KB ok, correct split
2 Correct 2 ms 6236 KB ok, correct split
3 Correct 2 ms 6236 KB ok, correct split
4 Correct 64 ms 18660 KB ok, correct split
5 Correct 51 ms 13364 KB ok, correct split
6 Correct 61 ms 29024 KB ok, correct split
7 Correct 64 ms 25940 KB ok, correct split
8 Correct 69 ms 16180 KB ok, correct split
9 Correct 48 ms 14980 KB ok, correct split
10 Correct 35 ms 12632 KB ok, correct split
11 Correct 33 ms 12632 KB ok, correct split
12 Correct 41 ms 12632 KB ok, correct split

Subtask #3
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 5976 KB ok, correct split
2 Incorrect 64 ms 13392 KB invalid split: #1=1, #2=39999, #3=60000
3 Halted 0 ms 0 KB -

Subtask #4
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 5976 KB ok, correct split
2 Correct 2 ms 6236 KB ok, no valid answer
3 Correct 2 ms 6236 KB ok, correct split
4 Correct 2 ms 6236 KB ok, correct split
5 Correct 2 ms 6232 KB ok, correct split
6 Incorrect 2 ms 6432 KB invalid split: #1=2, #2=3, #3=11
7 Halted 0 ms 0 KB -

Subtask #5
0 / 36.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 5976 KB ok, correct split
2 Correct 2 ms 6232 KB ok, correct split
3 Correct 2 ms 6236 KB ok, correct split
4 Incorrect 2 ms 6236 KB invalid split: #1=3, #2=0, #3=1
5 Halted 0 ms 0 KB -