Submission #379196

#	Time	Username	Problem	Language	Result	Execution time	Memory
379196		Thistle	Split the Attractions (IOI19_split)	C++14	0 / 100	94 ms	15084 KiB

split

#include "split.h"
#include<bits/stdc++.h>
#include<fstream>
using namespace std;

using ll=long long;
using H=pair<ll, ll>;
using vi=vector<ll>;
#define vec vector
#define rng(i,a,b) for(int (i)=(a);(i)<(b);(i)++)
#define rep(i,n) rng((i),(0),(n))
#define fs first
#define sc second
#define all(a) (a).begin(),(a).end()
#define siz(a) ll((a).size())
#define pb emplace_back

vector<int> find_split(int n, int a, int b, int c, vector<int> p, vector<int> q) {
	int m=siz(p);
	vec<H>e(m);
	rep(i,m){
		e[i]=H{p[i],q[i]};
	}
	vec<vi>f(n);
	rep(i,m) {
		f[e[i].fs].pb(e[i].sc);
		f[e[i].sc].pb(e[i].fs);
	}
	if(m==n-1){
		vi sz(n,0);
		auto dfs=[&](int x,int p,auto& dfs)->int{
			sz[x]=1;
			for(auto g:f[x]){
				if(g==p) continue;
				sz[x]+=dfs(g,x,dfs);
			}
			return sz[x];
		};dfs(0,-1,dfs);
		rep(i,n){
			for(auto g:f[i]){
				if(sz[g]>=min({a,b,c})){
					queue<int>q;
					q.push(g);
					vec<int>used(n,0);

					int k=0;
					if(a<=b&&a<=c) k=1;
					else if(b<=a&&b<=c) k=2;
					else k=3;

					used[g]=k;
					int sum=1;
					while(!q.empty()){
						int t=q.front();q.pop();
						for(auto g:f[t]){
							if(g==i) continue;
							if(!used[g]){
								if(sum==min({a,b,c})) continue;
								used[g]=k;
								q.push(g);
								sum++;
							}
						}
					}
					q.push(i);
					sum=1;
					int d=1,h=a;
					if(d==k) d=2,h=b;

					used[i]=d;
					while(!q.empty()){
						int t=q.front();q.pop();
						for(auto g:f[t]){
							if(!used[g]){
								if(sum==h) continue;
								used[g]=d;
								q.push(g);
								sum++;
							}
						}
					}
					int r=1;
					if(d!=1&&k!=1) r=1;
					else if(d!=2&&k!=2) r=2;
					else r=3;
					for(auto& g:used){
						if(g==0) g=r;
					}
					return used;
				}
			}
		}
		return vec<int>(n,0);
	}
	if(a==1){
		queue<int>que;
		que.push(0);
		vec<int>used(n,0);
		used[0]=2;int sum=1;
		while(!que.empty()){
			int t=que.front();que.pop();
			for(auto g:f[t]){
				if(!used[g]){
					if(sum==b) continue;
					used[g]=2;
					que.push(g);
					sum++;
				}
			}
		}
		rep(i,n) if(used[i]==0){
			used[i]=1;
			break;
		}
		rep(i,n) if(used[i]==0){
			used[i]=3;
		}
		return used;
	}
	return vec<int>(n,0);
}

Compilation message (stderr)

split.cpp: In function 'std::vector<int> find_split(int, int, int, int, std::vector<int>, std::vector<int>)':
split.cpp:10:28: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   10 | #define rng(i,a,b) for(int (i)=(a);(i)<(b);(i)++)
      |                            ^
split.cpp:11:18: note: in expansion of macro 'rng'
   11 | #define rep(i,n) rng((i),(0),(n))
      |                  ^~~
split.cpp:21:2: note: in expansion of macro 'rep'
   21 |  rep(i,m){
      |  ^~~
split.cpp:10:28: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   10 | #define rng(i,a,b) for(int (i)=(a);(i)<(b);(i)++)
      |                            ^
split.cpp:11:18: note: in expansion of macro 'rng'
   11 | #define rep(i,n) rng((i),(0),(n))
      |                  ^~~
split.cpp:25:2: note: in expansion of macro 'rep'
   25 |  rep(i,m) {
      |  ^~~
split.cpp:10:28: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   10 | #define rng(i,a,b) for(int (i)=(a);(i)<(b);(i)++)
      |                            ^
split.cpp:11:18: note: in expansion of macro 'rng'
   11 | #define rep(i,n) rng((i),(0),(n))
      |                  ^~~
split.cpp:39:3: note: in expansion of macro 'rep'
   39 |   rep(i,n){
      |   ^~~
split.cpp:10:28: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   10 | #define rng(i,a,b) for(int (i)=(a);(i)<(b);(i)++)
      |                            ^
split.cpp:11:18: note: in expansion of macro 'rng'
   11 | #define rep(i,n) rng((i),(0),(n))
      |                  ^~~
split.cpp:111:3: note: in expansion of macro 'rep'
  111 |   rep(i,n) if(used[i]==0){
      |   ^~~
split.cpp:10:28: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   10 | #define rng(i,a,b) for(int (i)=(a);(i)<(b);(i)++)
      |                            ^
split.cpp:11:18: note: in expansion of macro 'rng'
   11 | #define rep(i,n) rng((i),(0),(n))
      |                  ^~~
split.cpp:115:3: note: in expansion of macro 'rep'
  115 |   rep(i,n) if(used[i]==0){
      |   ^~~

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