Submission #379202

#	Time	Username	Problem	Language	Result	Execution time	Memory
379202		Thistle	Split the Attractions (IOI19_split)	C++14	0 / 100	113 ms	15340 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

struct unionfind{
	int n;
	vi pa,sz;
	int grp;
	unionfind(int n):n(n){
		pa.assign(n,-1);
		sz.assign(n,1);
		rep(i,n) pa[i]=i;
		grp=n;
	}
	int root(int x){
		if(x==pa[x]) return x;
		return pa[x]=root(pa[x]);
	}
	void unite(int x,int y){
		x=root(x);y=root(y);
		if(x==y) return;
		if(sz[x]>sz[y]) swap(x,y);
		sz[y]+=sz[x];
		pa[x]=y;
		grp--;
	}
};
mt19937 rnd;
void gen(){
	int n=rnd()%1000+3;
	int a=1;
	int b=rnd()%(n-2)+1;
	int c=n-a-b;
	int m=n-1+rnd()%1000;
	vi v;rep(i,n) v.pb(i);
	shuffle(all(v),rnd);
	vec<int>p,q;
	rep(i,n-1) p.push_back(i),q.pb(i+1);
	rng(i,n-1,m){
		int x=rnd()%n,y=rnd()%n;
		while(x==y) y=rnd()%n;
		p.pb(x);q.pb(y);
	}
	vec<int> ans=find_split(n,a,b,c,p,q);
	unionfind uf(n);
	rep(i,m){
		if(ans[p[i]]==2&&ans[q[i]]==2) uf.unite(p[i],q[i]);
	}
	int k=-1;
	rep(i,n) if(ans[i]==2) k=i;
	if(k<0) {
		cout<<n<<" "<<m<<endl;
		cout<<a<<" "<<b<<" "<<c<<endl;
		rep(i,m){
			cout<<p[i]<<" "<<q[i]<<endl;
		}
		for(auto g:ans) cout<<g;
		cout<<endl;
		exit(0);
	}
	rep(i,n) if(ans[i]==2){
		if(uf.root(i)!=uf.root(k)){
			cout<<n<<" "<<m<<endl;
			cout<<a<<" "<<b<<" "<<c<<endl;
			rep(i,m){
				cout<<p[i]<<" "<<q[i]<<endl;
			}
			for(auto g:ans) cout<<g;
			cout<<endl;
			exit(0);
		}
	}
}
void check(){
	rep(i,1000){
		gen();
		cout<<i<<endl;
	}
}

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 constructor 'unionfind::unionfind(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:25:3: note: in expansion of macro 'rep'
   25 |   rep(i,n) pa[i]=i;
      |   ^~~
split.cpp: In function 'void gen()':
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:48:7: note: in expansion of macro 'rep'
   48 |  vi v;rep(i,n) v.pb(i);
      |       ^~~
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:51:2: note: in expansion of macro 'rep'
   51 |  rep(i,n-1) p.push_back(i),q.pb(i+1);
      |  ^~~
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:52:2: note: in expansion of macro 'rng'
   52 |  rng(i,n-1,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:59:2: note: in expansion of macro 'rep'
   59 |  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:63:2: note: in expansion of macro 'rep'
   63 |  rep(i,n) if(ans[i]==2) k=i;
      |  ^~~
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:67:3: note: in expansion of macro 'rep'
   67 |   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:74:2: note: in expansion of macro 'rep'
   74 |  rep(i,n) if(ans[i]==2){
      |  ^~~
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:78:4: note: in expansion of macro 'rep'
   78 |    rep(i,m){
      |    ^~~
split.cpp: In function 'void check()':
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:88:2: note: in expansion of macro 'rep'
   88 |  rep(i,1000){
      |  ^~~
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:97:2: note: in expansion of macro 'rep'
   97 |  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:101:2: note: in expansion of macro 'rep'
  101 |  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:115:3: note: in expansion of macro 'rep'
  115 |   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:187:3: note: in expansion of macro 'rep'
  187 |   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:191:3: note: in expansion of macro 'rep'
  191 |   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