oj.uz

Submission #893434

# Submission time Handle Problem Language Result Execution time Memory
893434 2023-12-27T04:51:24 Z Faisal_Saqib Split the Attractions (IOI19_split) C++17
18 / 100
 94 ms 52940 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);
			for(int i=0;i<n;i++)
				if(ans[i]!=comp[0].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(0);
	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 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 67 ms 29760 KB ok, correct split
8 Correct 66 ms 23644 KB ok, correct split
9 Correct 47 ms 20500 KB ok, correct split
10 Correct 87 ms 52816 KB ok, correct split
11 Correct 72 ms 30800 KB ok, correct split

Subtask #2
11.0 / 11.0

# Verdict Execution time Memory 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 66 ms 20052 KB ok, correct split
5 Correct 34 ms 9308 KB ok, correct split
6 Correct 94 ms 52940 KB ok, correct split
7 Correct 60 ms 26052 KB ok, correct split
8 Correct 55 ms 11612 KB ok, correct split
9 Correct 35 ms 9564 KB ok, correct split
10 Correct 35 ms 9920 KB ok, correct split
11 Correct 31 ms 9928 KB ok, correct split
12 Correct 33 ms 9924 KB ok, correct split

Subtask #3
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 3676 KB ok, correct split
2 Incorrect 43 ms 9548 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 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 3672 KB invalid split: #1=1, #2=3, #3=7
5 Halted 0 ms 0 KB -

Subtask #5
0 / 36.0

# Verdict Execution time Memory 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 67 ms 29760 KB ok, correct split
8 Correct 66 ms 23644 KB ok, correct split
9 Correct 47 ms 20500 KB ok, correct split
10 Correct 87 ms 52816 KB ok, correct split
11 Correct 72 ms 30800 KB ok, correct split
12 Correct 1 ms 3672 KB ok, correct split
13 Correct 1 ms 3676 KB ok, correct split
14 Correct 1 ms 3676 KB ok, correct split
15 Correct 66 ms 20052 KB ok, correct split
16 Correct 34 ms 9308 KB ok, correct split
17 Correct 94 ms 52940 KB ok, correct split
18 Correct 60 ms 26052 KB ok, correct split
19 Correct 55 ms 11612 KB ok, correct split
20 Correct 35 ms 9564 KB ok, correct split
21 Correct 35 ms 9920 KB ok, correct split
22 Correct 31 ms 9928 KB ok, correct split
23 Correct 33 ms 9924 KB ok, correct split
24 Correct 1 ms 3676 KB ok, correct split
25 Incorrect 43 ms 9548 KB jury found a solution, contestant did not
26 Halted 0 ms 0 KB -