oj.uz

Submission #893509

# Submission time Handle Problem Language Result Execution time Memory
893509 2023-12-27T06:04:07 Z Faisal_Saqib Split the Attractions (IOI19_split) C++17
18 / 100
 74 ms 29044 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;
void df1(int x,int p)
{
	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 and !vis[y])
			df1(y,p);
}
void df2(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)
			df2(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;
		for(int y:ch[x])
		{
			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)
				{
					df2(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);
	for(int j=0;j<1;j++)
	{
		for(int i=0;i<n;i++)
			vis[i]=0;
		h[j]=0;
		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
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 5976 KB ok, correct split
2 Correct 2 ms 6236 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 1 ms 6236 KB ok, correct split
7 Correct 65 ms 28244 KB ok, correct split
8 Correct 62 ms 24172 KB ok, correct split
9 Correct 62 ms 22864 KB ok, correct split
10 Correct 63 ms 29044 KB ok, correct split
11 Correct 74 ms 29012 KB ok, correct split

Subtask #2
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 6232 KB ok, correct split
2 Correct 2 ms 6236 KB ok, correct split
3 Correct 2 ms 5980 KB ok, correct split
4 Correct 69 ms 21540 KB ok, correct split
5 Correct 47 ms 13396 KB ok, correct split
6 Correct 61 ms 29012 KB ok, correct split
7 Correct 65 ms 26192 KB ok, correct split
8 Correct 71 ms 16212 KB ok, correct split
9 Correct 48 ms 15188 KB ok, correct split
10 Correct 38 ms 12672 KB ok, correct split
11 Correct 35 ms 12656 KB ok, correct split
12 Correct 34 ms 12628 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 62 ms 13504 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 Correct 2 ms 5980 KB ok, correct split
2 Correct 1 ms 6236 KB ok, no valid answer
3 Correct 1 ms 5980 KB ok, correct split
4 Correct 2 ms 6236 KB ok, correct split
5 Correct 2 ms 6232 KB ok, correct split
6 Correct 3 ms 6236 KB ok, correct split
7 Correct 2 ms 6236 KB ok, correct split
8 Correct 3 ms 6236 KB ok, correct split
9 Correct 3 ms 6492 KB ok, correct split
10 Correct 3 ms 6492 KB ok, correct split
11 Correct 2 ms 6236 KB ok, correct split
12 Correct 5 ms 6492 KB ok, correct split
13 Correct 2 ms 5980 KB ok, correct split
14 Correct 2 ms 6072 KB ok, correct split
15 Correct 2 ms 6236 KB ok, correct split
16 Correct 2 ms 6232 KB ok, correct split
17 Correct 2 ms 6236 KB ok, correct split
18 Correct 2 ms 6232 KB ok, correct split
19 Correct 3 ms 6236 KB ok, correct split
20 Correct 2 ms 6236 KB ok, correct split
21 Correct 3 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

# Verdict Execution time Memory Grader output
1 Correct 2 ms 5976 KB ok, correct split
2 Correct 2 ms 6236 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 1 ms 6236 KB ok, correct split
7 Correct 65 ms 28244 KB ok, correct split
8 Correct 62 ms 24172 KB ok, correct split
9 Correct 62 ms 22864 KB ok, correct split
10 Correct 63 ms 29044 KB ok, correct split
11 Correct 74 ms 29012 KB ok, correct split
12 Correct 2 ms 6232 KB ok, correct split
13 Correct 2 ms 6236 KB ok, correct split
14 Correct 2 ms 5980 KB ok, correct split
15 Correct 69 ms 21540 KB ok, correct split
16 Correct 47 ms 13396 KB ok, correct split
17 Correct 61 ms 29012 KB ok, correct split
18 Correct 65 ms 26192 KB ok, correct split
19 Correct 71 ms 16212 KB ok, correct split
20 Correct 48 ms 15188 KB ok, correct split
21 Correct 38 ms 12672 KB ok, correct split
22 Correct 35 ms 12656 KB ok, correct split
23 Correct 34 ms 12628 KB ok, correct split
24 Correct 2 ms 5976 KB ok, correct split
25 Incorrect 62 ms 13504 KB jury found a solution, contestant did not
26 Halted 0 ms 0 KB -