oj.uz

답안 #893468

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
893468 2023-12-27T05:32:45 Z Faisal_Saqib Split the Attractions (IOI19_split) C++17
18 / 100
 85 ms 52816 KB 
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
const int N=1e5+2;
vector<int> ma[N],ans;
bool vis[N];
int n;
int sz[N],up[N],h[N];
pair<int,int> comp[3];
bool f=0;
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:ma[x])
		if(!vis[y] and ans[y]==comp[2].second)
			df1(y,p);
}
void dfs(int x,int q=-1)
{
	vis[x]=1;
	sz[x]=1;
	bool p=1;
	vector<int> c;
	for(int y:ma[x])
	{
		if(!vis[y])
		{
			up[y]=h[y]=h[x]+1;
			c.push_back(y);
			dfs(y,x);
			p&=(sz[y]<comp[0].first);
			sz[x]+=sz[y];
			up[x]=min(up[x],up[y]);
		}
		else
			up[x]=min(up[x],h[y]);
	}
	if(p and !f and sz[x]>=comp[0].first)
	{
		int P1=sz[x];
		int P2=n-P1;
		vector<int> b;
		for(int y:c)
		{
			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);
			if(q!=-1)
			  df1(q,1);
			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(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 1 ms 3672 KB ok, correct split
2 Correct 1 ms 3676 KB ok, correct split
3 Correct 1 ms 3676 KB ok, correct split
4 Correct 1 ms 3676 KB ok, correct split
5 Correct 1 ms 3676 KB ok, correct split
6 Correct 1 ms 3676 KB ok, correct split
7 Correct 73 ms 29720 KB ok, correct split
8 Correct 68 ms 38224 KB ok, correct split
9 Correct 51 ms 20724 KB ok, correct split
10 Correct 85 ms 52792 KB ok, correct split
11 Correct 66 ms 31064 KB ok, correct split

Subtask #2
11.0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 3676 KB ok, correct split
2 Correct 1 ms 3676 KB ok, correct split
3 Correct 1 ms 3672 KB ok, correct split
4 Correct 61 ms 20052 KB ok, correct split
5 Correct 35 ms 9296 KB ok, correct split
6 Correct 84 ms 52816 KB ok, correct split
7 Correct 62 ms 25424 KB ok, correct split
8 Correct 60 ms 11600 KB ok, correct split
9 Correct 34 ms 9808 KB ok, correct split
10 Correct 39 ms 9936 KB ok, correct split
11 Correct 33 ms 9916 KB ok, correct split
12 Correct 32 ms 9940 KB ok, correct split

Subtask #3
0 / 22.0

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

Subtask #4
0 / 24.0

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

Subtask #5
0 / 36.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 3672 KB ok, correct split
2 Correct 1 ms 3676 KB ok, correct split
3 Correct 1 ms 3676 KB ok, correct split
4 Correct 1 ms 3676 KB ok, correct split
5 Correct 1 ms 3676 KB ok, correct split
6 Correct 1 ms 3676 KB ok, correct split
7 Correct 73 ms 29720 KB ok, correct split
8 Correct 68 ms 38224 KB ok, correct split
9 Correct 51 ms 20724 KB ok, correct split
10 Correct 85 ms 52792 KB ok, correct split
11 Correct 66 ms 31064 KB ok, correct split
12 Correct 1 ms 3676 KB ok, correct split
13 Correct 1 ms 3676 KB ok, correct split
14 Correct 1 ms 3672 KB ok, correct split
15 Correct 61 ms 20052 KB ok, correct split
16 Correct 35 ms 9296 KB ok, correct split
17 Correct 84 ms 52816 KB ok, correct split
18 Correct 62 ms 25424 KB ok, correct split
19 Correct 60 ms 11600 KB ok, correct split
20 Correct 34 ms 9808 KB ok, correct split
21 Correct 39 ms 9936 KB ok, correct split
22 Correct 33 ms 9916 KB ok, correct split
23 Correct 32 ms 9940 KB ok, correct split
24 Correct 1 ms 3672 KB ok, correct split
25 Incorrect 41 ms 9476 KB jury found a solution, contestant did not
26 Halted 0 ms 0 KB -