oj.uz

Submission #295160

# Submission time Handle Problem Language Result Execution time Memory
295160 2020-09-09T14:01:39 Z AKaan37 Split the Attractions (IOI19_split) C++17
22 / 100
 172 ms 24568 KB 
#include "split.h"
#include <bits/stdc++.h>

using namespace std;

typedef long long lo;
typedef pair< lo,lo > PII;

#define fi first
#define se second
#define mp make_pair
#define endl "\n"
#define pb push_back
#define fio() ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)
#define FOR for(int i=1;i<=n;i++)
#define mid ((start+end)/2)
#define ort ((bas+son)/2)

const lo inf = 2000000000;
const lo KOK = 100000;
const lo LOG = 30;
const lo li = 500005;
const lo mod = 1000000007;

int n,m,b[li],a[li],k,flag,t,ind,mn=inf,mx,mx1,par[li],vis[li],say,gel,sub[li];
int cev;
string s;
vector<int> v[li];

inline void dfs(int node,int ata){
	if(vis[node])return;
	sub[node]=1;
	for(int i=0;i<(int)v[node].size();i++){
		int go=v[node][i];
		if(go==ata)continue;
		if(vis[go])continue;
		dfs(go,node);
		sub[node]+=sub[go];
	}
	par[node]=ata;
	if(sub[node]>=mx && sub[node]<mn){ind=node;mn=sub[node];}
}

inline void dfs1(int node,int ata,int aa,int bb,int cc){
	if(vis[node])return;
	if(say>=mx)return ;
	if(mx==aa && (b[1]==0 || b[1]==gel)){vis[node]=1;b[1]=gel;say++;}
	else if(mx==bb && (b[2]==0 || b[2]==gel)){vis[node]=2;b[2]=gel;say++;}
	else if(mx==cc && (b[3]==0 || b[3]==gel)){vis[node]=3;b[3]=gel;say++;}
	if(say>=mx)return ;
	for(int i=0;i<(int)v[node].size();i++){
		int go=v[node][i];
		if(go==ata)continue;
		dfs1(go,node,aa,bb,cc);
	}
}

inline void dfs3(int node,int bb,int cc){
	if(say>=mx)return ;
	if(vis[node])return ;
	//~ if(mx==aa){vis[node]=1;b[1]=1;say++;}
	if(mx==bb){vis[node]=2;b[2]=1;say++;}
	else if(mx==cc){vis[node]=3;b[3]=1;say++;}
	if(say>=mx)return;
	for(int i=0;i<(int)v[node].size();i++){
		int go=v[node][i];
		dfs3(go,bb,cc);
	}
}

vector<int> find_split(int n, int aa, int bb, int cc, vector<int> p, vector<int> q) {
	if((int)p.size()==n-1){
		flag=0;
		vector<int> res;
		a[1]=aa;
		a[2]=bb;
		a[3]=cc;
		sort(a+1,a+4);
		mx=a[1];
		mx1=a[2];
		for(int i=0;i<(int)p.size();i++){
			v[p[i]].pb(q[i]);
			v[q[i]].pb(p[i]);
		}
		gel=1;
		ind=-1;
		dfs(0,-1);
		if(ind==-1){
			flag=1;
		}
		dfs1(ind,par[ind],aa,bb,cc);
		mx=mx1;
		gel=2;
		say=0;
		mn=inf;
		ind=-1;
		dfs(0,-1);
		if(ind==-1){
			flag=1;
		}
		dfs1(ind,par[ind],aa,bb,cc);
		if(flag==0){
			for(int i=0;i<n;i++){
				if(vis[i])res.pb(vis[i]);
				else{
					if(b[1]==0)res.pb(1);
					if(b[2]==0)res.pb(2);
					if(b[3]==0)res.pb(3);
				}
			}
			return res;
		}
		res.clear();
		memset(vis,0,sizeof(vis));
		memset(b,0,sizeof(b));
		a[1]=aa;
		a[2]=bb;
		a[3]=cc;
		sort(a+1,a+4);
		mx=a[2];
		FOR v[i-1].clear();
		mx1=a[1];
		for(int i=0;i<(int)p.size();i++){
			v[p[i]].pb(q[i]);
			v[q[i]].pb(p[i]);
		}
		say=0;
		mn=inf;
		gel=1;
		ind=-1;
		dfs(0,-1);
		if(ind==-1){
			FOR res.pb(0);
			return res;
		}
		dfs1(ind,par[ind],aa,bb,cc);
		mx=mx1;
		gel=2;
		say=0;
		mn=inf;
		ind=-1;
		dfs(0,-1);
		if(ind==-1){
			FOR res.pb(0);
			return res;
		}
		dfs1(ind,par[ind],aa,bb,cc);
		//~ if(flag==0){
			for(int i=0;i<n;i++){
				if(vis[i])res.pb(vis[i]);
				else{
					if(b[1]==0)res.pb(1);
					if(b[2]==0)res.pb(2);
					if(b[3]==0)res.pb(3);
				}
			}
			
		//~ }
		return res;
	}
	vector<int> res;
	a[1]=aa;
	a[2]=bb;
	a[3]=cc;
	sort(a+1,a+3+1);
	mx=a[2];
	say=0;
	dfs3(0,bb,cc);
	for(int i=0;i<n;i++){
		//~ if(vis[i])res.pb(vis[i]);
		//~ else{
			if(aa){res.pb(1);aa=0;}
			else if(mx){res.pb(2);mx--;}
			else res.pb(3);
		//~ }
	}
	return res;
}

Subtask #1
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 12032 KB ok, correct split
2 Correct 9 ms 12032 KB ok, correct split
3 Correct 8 ms 12032 KB ok, correct split
4 Incorrect 9 ms 12032 KB invalid split: #1=1, #2=1, #3=2
5 Halted 0 ms 0 KB -

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 12032 KB ok, correct split
2 Correct 8 ms 12032 KB ok, correct split
3 Correct 9 ms 12032 KB ok, correct split
4 Correct 66 ms 16500 KB ok, correct split
5 Correct 109 ms 19832 KB ok, correct split
6 Correct 54 ms 15476 KB ok, correct split
7 Correct 134 ms 23800 KB ok, correct split
8 Incorrect 79 ms 17140 KB 2 components are not connected
9 Halted 0 ms 0 KB -

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 12032 KB ok, correct split
2 Correct 139 ms 22908 KB ok, correct split
3 Correct 41 ms 15232 KB ok, correct split
4 Correct 9 ms 12032 KB ok, correct split
5 Correct 134 ms 21576 KB ok, correct split
6 Correct 133 ms 21624 KB ok, correct split
7 Correct 169 ms 24568 KB ok, correct split
8 Correct 160 ms 22008 KB ok, correct split
9 Correct 172 ms 24440 KB ok, correct split
10 Correct 42 ms 18552 KB ok, no valid answer
11 Correct 59 ms 19576 KB ok, no valid answer
12 Correct 122 ms 23132 KB ok, no valid answer
13 Correct 166 ms 22904 KB ok, no valid answer
14 Correct 86 ms 23280 KB ok, no valid answer

Subtask #4
0 / 24.0

# Verdict Execution time Memory Grader output
1 Incorrect 8 ms 12032 KB invalid split: #1=1, #2=3, #3=5
2 Halted 0 ms 0 KB -

Subtask #5
0 / 36.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 12032 KB ok, correct split
2 Correct 9 ms 12032 KB ok, correct split
3 Correct 8 ms 12032 KB ok, correct split
4 Incorrect 9 ms 12032 KB invalid split: #1=1, #2=1, #3=2
5 Halted 0 ms 0 KB -