oj.uz

Submission #295182

# Submission time Handle Problem Language Result Execution time Memory
295182 2020-09-09T14:09:35 Z AKaan37 Split the Attractions (IOI19_split) C++17
22 / 100
 155 ms 24060 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 && aa!=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;
	res.clear();
	a[1]=aa;
	a[2]=bb;
	a[3]=cc;
	sort(a+1,a+3+1);
	mx=a[2];
	say=0;
	dfs3(0,bb,cc);
	res.clear();
	for(int i=0;i<n;i++){
		if(vis[i])res.pb(vis[i]);
		else{
			if(aa){res.pb(1);aa=0;}
			else if(b[2]==0)res.pb(2);
			else if(b[3]==0)res.pb(3);
		}
	}
	//~ 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 8 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 8 ms 12032 KB ok, correct split
2 Correct 8 ms 12032 KB ok, correct split
3 Incorrect 9 ms 12080 KB invalid split: #1=1, #2=1, #3=3
4 Halted 0 ms 0 KB -

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 12160 KB ok, correct split
2 Correct 131 ms 22520 KB ok, correct split
3 Correct 36 ms 15096 KB ok, correct split
4 Correct 9 ms 12032 KB ok, correct split
5 Correct 121 ms 21112 KB ok, correct split
6 Correct 134 ms 21112 KB ok, correct split
7 Correct 155 ms 24060 KB ok, correct split
8 Correct 123 ms 21624 KB ok, correct split
9 Correct 150 ms 24056 KB ok, correct split
10 Correct 36 ms 18432 KB ok, no valid answer
11 Correct 49 ms 19320 KB ok, no valid answer
12 Correct 89 ms 22900 KB ok, no valid answer
13 Correct 112 ms 22520 KB ok, no valid answer
14 Correct 78 ms 22896 KB ok, no valid answer

Subtask #4
0 / 24.0

# Verdict Execution time Memory Grader output
1 Incorrect 10 ms 12032 KB invalid split: #1=1, #2=7, #3=1
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 8 ms 12032 KB invalid split: #1=1, #2=1, #3=2
5 Halted 0 ms 0 KB -