oj.uz

Submission #893470

# Submission time Handle Problem Language Result Execution time Memory
893470 2023-12-27T05:35:42 Z Faisal_Saqib Split the Attractions (IOI19_split) C++17
18 / 100
 82 ms 33636 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];
		int sh=-1;
		sort(begin(cop),end(cop),sorter);
		for(int y:cop)
		{
			if(up[y]<h[x] and (P1-sz[y])>=comp[0].first)
			{
				sh=y;
				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);
			f=1;
			if(x!=0)
				df1(0,1);
			else if(sh!=-1)
				df1(sh,1);
			else
				f=0;
		}
	}
}
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 3 ms 6236 KB ok, correct split
2 Correct 2 ms 6068 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 66 ms 32676 KB ok, correct split
8 Correct 62 ms 27472 KB ok, correct split
9 Correct 61 ms 25712 KB ok, correct split
10 Correct 64 ms 33620 KB ok, correct split
11 Correct 64 ms 33620 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 6236 KB ok, correct split
4 Correct 68 ms 23592 KB ok, correct split
5 Correct 46 ms 13536 KB ok, correct split
6 Correct 66 ms 33636 KB ok, correct split
7 Correct 70 ms 29264 KB ok, correct split
8 Correct 82 ms 16124 KB ok, correct split
9 Correct 49 ms 15184 KB ok, correct split
10 Correct 34 ms 12800 KB ok, correct split
11 Correct 36 ms 12620 KB ok, correct split
12 Correct 31 ms 12624 KB ok, correct split

Subtask #3
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 6488 KB ok, correct split
2 Incorrect 47 ms 13396 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 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 3 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 2 ms 6068 KB ok, correct split
8 Correct 1 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 3 ms 6492 KB ok, correct split
13 Correct 2 ms 6232 KB ok, correct split
14 Correct 2 ms 6236 KB ok, correct split
15 Correct 2 ms 6236 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 6232 KB ok, correct split
20 Correct 2 ms 6392 KB ok, correct split
21 Correct 3 ms 6492 KB ok, correct split
22 Incorrect 3 ms 6488 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 3 ms 6236 KB ok, correct split
2 Correct 2 ms 6068 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 66 ms 32676 KB ok, correct split
8 Correct 62 ms 27472 KB ok, correct split
9 Correct 61 ms 25712 KB ok, correct split
10 Correct 64 ms 33620 KB ok, correct split
11 Correct 64 ms 33620 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 6236 KB ok, correct split
15 Correct 68 ms 23592 KB ok, correct split
16 Correct 46 ms 13536 KB ok, correct split
17 Correct 66 ms 33636 KB ok, correct split
18 Correct 70 ms 29264 KB ok, correct split
19 Correct 82 ms 16124 KB ok, correct split
20 Correct 49 ms 15184 KB ok, correct split
21 Correct 34 ms 12800 KB ok, correct split
22 Correct 36 ms 12620 KB ok, correct split
23 Correct 31 ms 12624 KB ok, correct split
24 Correct 2 ms 6488 KB ok, correct split
25 Incorrect 47 ms 13396 KB jury found a solution, contestant did not
26 Halted 0 ms 0 KB -