oj.uz

Submission #295130

# Submission time Handle Problem Language Result Execution time Memory
295130 2020-09-09T13:39:40 Z AKaan37 Split the Attractions (IOI19_split) C++17
22 / 100
 639 ms 1048580 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);
	}
}

vector<int> find_split(int n, int aa, int bb, int cc, vector<int> p, vector<int> q) {
	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;
}

Subtask #1
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 12032 KB ok, correct split
2 Runtime error 628 ms 1048580 KB Execution killed with signal 9
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 Runtime error 610 ms 1048580 KB Execution killed with signal 9
3 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 145 ms 22284 KB ok, correct split
3 Correct 38 ms 14840 KB ok, correct split
4 Correct 11 ms 12032 KB ok, correct split
5 Correct 131 ms 21112 KB ok, correct split
6 Correct 141 ms 21104 KB ok, correct split
7 Correct 176 ms 23800 KB ok, correct split
8 Correct 134 ms 21368 KB ok, correct split
9 Correct 185 ms 23840 KB ok, correct split
10 Correct 43 ms 18296 KB ok, no valid answer
11 Correct 53 ms 19168 KB ok, no valid answer
12 Correct 98 ms 22516 KB ok, no valid answer
13 Correct 119 ms 22264 KB ok, no valid answer
14 Correct 94 ms 22640 KB ok, no valid answer

Subtask #4
0 / 24.0

# Verdict Execution time Memory Grader output
1 Runtime error 639 ms 1048580 KB Execution killed with signal 9
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 Runtime error 628 ms 1048580 KB Execution killed with signal 9
3 Halted 0 ms 0 KB -