oj.uz

Submission #893458

# Submission time Handle Problem Language Result Execution time Memory
893458 2023-12-27T05:11:46 Z Faisal_Saqib Split the Attractions (IOI19_split) C++17
18 / 100
 721 ms 1048576 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);
	for(int j=0;j<n;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 6236 KB ok, correct split
2 Correct 1 ms 6236 KB ok, correct split
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 Correct 2 ms 6236 KB ok, correct split
7 Correct 77 ms 31200 KB ok, correct split
8 Correct 67 ms 26448 KB ok, correct split
9 Correct 65 ms 24784 KB ok, correct split
10 Correct 64 ms 32080 KB ok, correct split
11 Correct 80 ms 32084 KB ok, correct split

Subtask #2
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 6236 KB ok, correct split
2 Correct 2 ms 6236 KB ok, correct split
3 Correct 2 ms 6236 KB ok, correct split
4 Correct 73 ms 22776 KB ok, correct split
5 Correct 47 ms 13500 KB ok, correct split
6 Correct 78 ms 32084 KB ok, correct split
7 Correct 68 ms 28328 KB ok, correct split
8 Correct 78 ms 16208 KB ok, correct split
9 Correct 50 ms 15188 KB ok, correct split
10 Correct 37 ms 12876 KB ok, correct split
11 Correct 47 ms 12668 KB ok, correct split
12 Correct 38 ms 12760 KB ok, correct split

Subtask #3
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 6236 KB ok, correct split
2 Runtime error 721 ms 1048576 KB Execution killed with signal 9
3 Halted 0 ms 0 KB -

Subtask #4
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 6232 KB ok, correct split
2 Runtime error 523 ms 1048576 KB Execution killed with signal 9
3 Halted 0 ms 0 KB -

Subtask #5
0 / 36.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 6236 KB ok, correct split
2 Correct 1 ms 6236 KB ok, correct split
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 Correct 2 ms 6236 KB ok, correct split
7 Correct 77 ms 31200 KB ok, correct split
8 Correct 67 ms 26448 KB ok, correct split
9 Correct 65 ms 24784 KB ok, correct split
10 Correct 64 ms 32080 KB ok, correct split
11 Correct 80 ms 32084 KB ok, correct split
12 Correct 2 ms 6236 KB ok, correct split
13 Correct 2 ms 6236 KB ok, correct split
14 Correct 2 ms 6236 KB ok, correct split
15 Correct 73 ms 22776 KB ok, correct split
16 Correct 47 ms 13500 KB ok, correct split
17 Correct 78 ms 32084 KB ok, correct split
18 Correct 68 ms 28328 KB ok, correct split
19 Correct 78 ms 16208 KB ok, correct split
20 Correct 50 ms 15188 KB ok, correct split
21 Correct 37 ms 12876 KB ok, correct split
22 Correct 47 ms 12668 KB ok, correct split
23 Correct 38 ms 12760 KB ok, correct split
24 Correct 2 ms 6236 KB ok, correct split
25 Runtime error 721 ms 1048576 KB Execution killed with signal 9
26 Halted 0 ms 0 KB -