oj.uz

답안 #893454

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
893454 2023-12-27T05:06:47 Z Faisal_Saqib Split the Attractions (IOI19_split) C++17
18 / 100
 69 ms 32120 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 n;
int sz[N],up[N],h[N];
pair<int,int> comp[3];
bool f=0;
bool sorter(int x,int y)
{
	return sz[x]>=sz[y];
}
void df1(int x,int p)
{
	if(comp[p].first==0)
		return;
	vis[x]=1;
	if(comp[p].first>0)
	{
		ans[x]=comp[p].second;
		comp[p].first--;
	}
	for(int y:ch[x])
		if(ans[y]==comp[2].second)
			df1(y,p);
}
void dfs_ch(int x)
{
	vis[x]=1;
	for(int y:ma[x])
	{
		if(!vis[y])
		{
			dfs_ch(y);
			ch[x].push_back(y);
		}
	}
}
void dfs(int x,int q=-1)
{
	sz[x]=1;
	bool p=1;
	for(int y:ma[x])
		if(vis[y])
			up[x]=min(up[x],h[y]);
	for(int y:ch[x])
	{
		up[y]=h[y]=h[x]+1;
		dfs(y,x);
		p&=(sz[y]<comp[0].first);
		sz[x]+=sz[y];
		up[x]=min(up[x],up[y]);
	}
	if(p and !f and sz[x]>=comp[0].first)
	{
		int P1=sz[x];
		int P2=n-P1;
		vector<int> b;
		vector<int> cop=ch[x];
		sort(begin(cop),end(cop),sorter);
		for(int y:cop)
		{
			if(up[y]<h[x] and (P1-sz[y])>=comp[0].first)
				P1-=sz[y],P2+=sz[y];
			else
				b.push_back(y);
		}	
		if(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(auto i:b)
				df1(i,0);
			for(int i=0;i<n;i++)
				if(ans[i]==comp[2].second)
				{
					df1(i,1);
					break;
				}
			f=1;
		}
	}
}
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);
	dfs_ch(0);
	for(int i=0;i<n;i++)
		vis[i]=0;
	dfs(0);
	if(!f)
		for(int i=0;i<n;i++)
			ans[i]=0;
	return ans;
}

Subtask #1
7.0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 6232 KB ok, correct split
2 Correct 1 ms 6232 KB ok, correct split
3 Correct 2 ms 6236 KB ok, correct split
4 Correct 2 ms 6236 KB ok, correct split
5 Correct 2 ms 6236 KB ok, correct split
6 Correct 2 ms 6236 KB ok, correct split
7 Correct 65 ms 31316 KB ok, correct split
8 Correct 62 ms 26284 KB ok, correct split
9 Correct 59 ms 24660 KB ok, correct split
10 Correct 63 ms 32080 KB ok, correct split
11 Correct 69 ms 32084 KB ok, correct split

Subtask #2
11.0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 6232 KB ok, correct split
2 Correct 2 ms 6232 KB ok, correct split
3 Correct 2 ms 6232 KB ok, correct split
4 Correct 66 ms 22756 KB ok, correct split
5 Correct 47 ms 13396 KB ok, correct split
6 Correct 64 ms 32120 KB ok, correct split
7 Correct 65 ms 28252 KB ok, correct split
8 Correct 68 ms 16212 KB ok, correct split
9 Correct 48 ms 15184 KB ok, correct split
10 Correct 33 ms 12572 KB ok, correct split
11 Correct 35 ms 12884 KB ok, correct split
12 Correct 37 ms 12616 KB ok, correct split

Subtask #3
0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 6236 KB ok, correct split
2 Incorrect 46 ms 13392 KB jury found a solution, contestant did not
3 Halted 0 ms 0 KB -

Subtask #4
0 / 24.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 6232 KB ok, correct split
2 Correct 1 ms 6232 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 1 ms 6236 KB ok, correct split
6 Correct 2 ms 6232 KB ok, correct split
7 Correct 2 ms 6236 KB ok, correct split
8 Correct 2 ms 6236 KB ok, correct split
9 Correct 3 ms 6640 KB ok, correct split
10 Correct 3 ms 6492 KB ok, correct split
11 Correct 2 ms 6236 KB ok, correct split
12 Correct 3 ms 6492 KB ok, correct split
13 Correct 2 ms 6236 KB ok, correct split
14 Correct 2 ms 6236 KB ok, correct split
15 Correct 2 ms 6232 KB ok, correct split
16 Correct 2 ms 6236 KB ok, correct split
17 Correct 2 ms 6236 KB ok, correct split
18 Correct 2 ms 6236 KB ok, correct split
19 Correct 2 ms 6224 KB ok, correct split
20 Correct 2 ms 6236 KB ok, correct split
21 Correct 2 ms 6492 KB ok, correct split
22 Incorrect 2 ms 6492 KB jury found a solution, contestant did not
23 Halted 0 ms 0 KB -

Subtask #5
0 / 36.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 6232 KB ok, correct split
2 Correct 1 ms 6232 KB ok, correct split
3 Correct 2 ms 6236 KB ok, correct split
4 Correct 2 ms 6236 KB ok, correct split
5 Correct 2 ms 6236 KB ok, correct split
6 Correct 2 ms 6236 KB ok, correct split
7 Correct 65 ms 31316 KB ok, correct split
8 Correct 62 ms 26284 KB ok, correct split
9 Correct 59 ms 24660 KB ok, correct split
10 Correct 63 ms 32080 KB ok, correct split
11 Correct 69 ms 32084 KB ok, correct split
12 Correct 2 ms 6232 KB ok, correct split
13 Correct 2 ms 6232 KB ok, correct split
14 Correct 2 ms 6232 KB ok, correct split
15 Correct 66 ms 22756 KB ok, correct split
16 Correct 47 ms 13396 KB ok, correct split
17 Correct 64 ms 32120 KB ok, correct split
18 Correct 65 ms 28252 KB ok, correct split
19 Correct 68 ms 16212 KB ok, correct split
20 Correct 48 ms 15184 KB ok, correct split
21 Correct 33 ms 12572 KB ok, correct split
22 Correct 35 ms 12884 KB ok, correct split
23 Correct 37 ms 12616 KB ok, correct split
24 Correct 2 ms 6236 KB ok, correct split
25 Incorrect 46 ms 13392 KB jury found a solution, contestant did not
26 Halted 0 ms 0 KB -