Submission #332390

#	Time	Username	Problem	Language	Result	Execution time	Memory
332390		nicholask	Split the Attractions (IOI19_split)	C++14	0 / 100	92 ms	10732 KiB

split

#include "split.h"
#include <bits/stdc++.h>
using namespace std;
int realans[4];
vector <int> g[100005];
bool satisfy_sub1(int n){
	for (int i=0; i<n; i++){
		if (g[i].size()>2) return 0;
	}
	return 1;
}
vector <int> find_split(int n,int a,int b,int c,vector <int> p,vector <int> q){
	int ord[4]={0,a,b,c};
	bool used[4]={0,0,0,0};
	sort(ord,ord+4);
	for (int i=1; i<=3; i++){
		if (a==ord[i]&&!used[i]){
			realans[1]=i;
			used[i]=1;
			break;
		}
	}
	for (int i=1; i<=3; i++){
		if (b==ord[i]&&!used[i]){
			realans[2]=i;
			used[i]=1;
			break;
		}
	}
	for (int i=1; i<=3; i++){
		if (c==ord[i]&&!used[i]){
			realans[3]=i;
			used[i]=1;
			break;
		}
	}
	a=ord[1];
	b=ord[2];
	c=ord[3];
	int m=p.size();
	for (int i=0; i<m; i++){
		g[p[i]].push_back(q[i]);
		g[q[i]].push_back(p[i]);
	}
	bool donea=0,doneb=0;
	vector <int> ans(n,0);
	if (satisfy_sub1(n)){
		bool vis[n];
		for (int i=0; i<n; i++) vis[i]=0;
		for (int i=0; i<n; i++){
			if (vis[i]) continue;
			queue <int> al,qu;
			qu.push(i);
			al.push(i);
			vis[i]=1;
			while (!qu.empty()){
				int t=qu.front();
				qu.pop();
				for (auto&j:g[t]){
					if (!vis[j]||i==j&&al.size()>2){
						qu.push(j);
						al.push(j);
						vis[j]=1;
						break;
					}
				}
			}
			if (al.size()>3) al.pop();
			int als=al.size();
			if (als<a) continue;
			if (!donea&&!doneb&&als>=a+b){
				for (int j=0; j<a; j++){
					ans[al.front()]=1;
					al.pop();
				}
				for (int j=0; j<b; j++){
					ans[al.front()]=2;
					al.pop();
				}
				donea=1;
				doneb=1;
			} else if (!doneb&&als>=b){
				for (int j=0; j<b; j++){
					ans[al.front()]=2;
					al.pop();
				}
				doneb=1;
			} else if (!donea&&als>=a){
				for (int j=0; j<a; j++){
					ans[al.front()]=1;
					al.pop();
				}
				donea=1;
			}
			if (donea&&doneb) goto die1;
		}
		for (int i=0; i<n; i++) ans[i]=0;
		return ans;
		die1:;
		for (int i=0; i<n; i++){
			if (ans[i]==1) ans[i]=realans[1];
			else if (ans[i]==2) ans[i]=realans[2];
			else ans[i]=realans[3]; 
		}
		return ans;
	}
}
/*
int main(){
	int n,a,b,c;
	cin>>n>>a>>b>>c;
	int m;
	cin>>m;
	vector <int> p,q;
	for (int i=0; i<m; i++){
		int t;
		cin>>t;
		p.push_back(t);
	}
	for (int i=0; i<m; i++){
		int t;
		cin>>t;
		q.push_back(t);
	}
	vector <int> ans=find_split(n,a,b,c,p,q);
	cout<<realans[1]<<' '<<realans[2]<<' '<<realans[3]<<endl;
	for (auto&i:ans) cout<<i<<' '; 
}
*/

Compilation message (stderr)

split.cpp: In function 'std::vector<int> find_split(int, int, int, int, std::vector<int>, std::vector<int>)':
split.cpp:60:23: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   60 |      if (!vis[j]||i==j&&al.size()>2){
      |                   ~~~~^~~~~~~~~~~~~
split.cpp:107:1: warning: control reaches end of non-void function [-Wreturn-type]
  107 | }
      | ^

• Subtask 1: 0 / 7
• Subtask 2: 0 / 11
• Subtask 3: 0 / 22
• Subtask 4: 0 / 24
• Subtask 5: 0 / 36