oj.uz

답안 #893562

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
893562 2023-12-27T07:04:44 Z Faisal_Saqib Split the Attractions (IOI19_split) C++17
11 / 100
 99 ms 29036 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(vis[x])
		return;
	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(vis[x])
		return;
	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

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 5980 KB ok, correct split
2 Correct 2 ms 6236 KB ok, correct split
3 Correct 2 ms 5980 KB ok, correct split
4 Incorrect 2 ms 5980 KB invalid split: #1=3, #2=1, #3=0
5 Halted 0 ms 0 KB -

Subtask #2
11.0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 6236 KB ok, correct split
2 Correct 2 ms 6236 KB ok, correct split
3 Correct 2 ms 6492 KB ok, correct split
4 Correct 72 ms 18636 KB ok, correct split
5 Correct 58 ms 13536 KB ok, correct split
6 Correct 73 ms 29036 KB ok, correct split
7 Correct 81 ms 25940 KB ok, correct split
8 Correct 99 ms 16212 KB ok, correct split
9 Correct 76 ms 15176 KB ok, correct split
10 Correct 50 ms 12708 KB ok, correct split
11 Correct 35 ms 12632 KB ok, correct split
12 Correct 37 ms 12656 KB ok, correct split

Subtask #3
0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 5980 KB ok, correct split
2 Incorrect 54 ms 13436 KB invalid split: #1=0, #2=40000, #3=60000
3 Halted 0 ms 0 KB -

Subtask #4
0 / 24.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 6232 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 1 ms 6236 KB ok, correct split
5 Correct 2 ms 6236 KB ok, correct split
6 Incorrect 2 ms 6236 KB invalid split: #1=3, #2=0, #3=13
7 Halted 0 ms 0 KB -

Subtask #5
0 / 36.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 5980 KB ok, correct split
2 Correct 2 ms 6236 KB ok, correct split
3 Correct 2 ms 5980 KB ok, correct split
4 Incorrect 2 ms 5980 KB invalid split: #1=3, #2=1, #3=0
5 Halted 0 ms 0 KB -