oj.uz

Submission #295168

# Submission time Handle Problem Language Result Execution time Memory
295168 2020-09-09T14:05:09 Z AKaan37 Split the Attractions (IOI19_split) C++17
22 / 100
 175 ms 23800 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(bb){bb--;res.pb(1);}
		else res.pb(2);
	}
	//~ 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 Incorrect 9 ms 12032 KB invalid split: #1=1, #2=2, #3=0
3 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 Incorrect 8 ms 12032 KB invalid split: #1=1, #2=2, #3=0
3 Halted 0 ms 0 KB -

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 12032 KB ok, correct split
2 Correct 138 ms 22264 KB ok, correct split
3 Correct 39 ms 14848 KB ok, correct split
4 Correct 9 ms 12032 KB ok, correct split
5 Correct 140 ms 20984 KB ok, correct split
6 Correct 140 ms 20984 KB ok, correct split
7 Correct 169 ms 23800 KB ok, correct split
8 Correct 140 ms 21476 KB ok, correct split
9 Correct 175 ms 23800 KB ok, correct split
10 Correct 37 ms 18296 KB ok, no valid answer
11 Correct 54 ms 19192 KB ok, no valid answer
12 Correct 102 ms 22504 KB ok, no valid answer
13 Correct 125 ms 22220 KB ok, no valid answer
14 Correct 83 ms 22624 KB ok, no valid answer

Subtask #4
0 / 24.0

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