oj.uz

Submission #295209

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

using namespace std;

typedef long long lo;
typedef pair< int,int > 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;
pair<int,int> p[10];
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 ne){
	if(say>=mx)return ;
	if(vis[node])return ;
	say++;
	vis[node]=ne;
	if(say>=mx)return;
	for(int i=0;i<(int)v[node].size();i++){
		int go=v[node][i];
		dfs3(go,ne);
	}
}

vector<int> find_split(int n, int aa, int bb, int cc, vector<int> pp, vector<int> q) {
	if((int)pp.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)pp.size();i++){
			v[pp[i]].pb(q[i]);
			v[q[i]].pb(pp[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)pp.size();i++){
			v[pp[i]].pb(q[i]);
			v[q[i]].pb(pp[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();
	for(int i=0;i<(int)pp.size();i++){
		v[pp[i]].pb(q[i]);
		v[q[i]].pb(pp[i]);
	}
	p[1]=mp(aa,1);
	p[2]={bb,2};
	p[3]={cc,3};
	sort(p+1,p+4);
	mx=p[2].fi;
	say=0;
	dfs3(0,p[2].se);
	for(int i=0;i<n;i++){
		say=0;
		if(vis[i]==0){dfs3(i,p[1].se);break;}
	}
	res.clear();
	for(int i=0;i<n;i++){
		if(vis[i]==0)vis[i]=p[3].se;
		res.pb(vis[i]);
	}
	//~ res.pb(3);
	return res;
}

Subtask #1
0 / 7.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 8 ms 12032 KB ok, correct split
5 Correct 9 ms 12032 KB ok, correct split
6 Incorrect 8 ms 12032 KB invalid split: #1=40, #2=40, #3=20
7 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 Incorrect 9 ms 12032 KB invalid split: #1=2, #2=2, #3=1
4 Halted 0 ms 0 KB -

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 12032 KB ok, correct split
2 Correct 122 ms 22280 KB ok, correct split
3 Correct 36 ms 14840 KB ok, correct split
4 Correct 8 ms 12032 KB ok, correct split
5 Correct 117 ms 20984 KB ok, correct split
6 Correct 121 ms 20984 KB ok, correct split
7 Correct 158 ms 23932 KB ok, correct split
8 Correct 127 ms 21496 KB ok, correct split
9 Correct 149 ms 23800 KB ok, correct split
10 Correct 35 ms 18296 KB ok, no valid answer
11 Correct 49 ms 19192 KB ok, no valid answer
12 Correct 87 ms 22516 KB ok, no valid answer
13 Correct 113 ms 22264 KB ok, no valid answer
14 Correct 75 ms 22640 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=5, #2=1, #3=3
2 Halted 0 ms 0 KB -

Subtask #5
0 / 36.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 8 ms 12032 KB ok, correct split
5 Correct 9 ms 12032 KB ok, correct split
6 Incorrect 8 ms 12032 KB invalid split: #1=40, #2=40, #3=20
7 Halted 0 ms 0 KB -