Submission #379322

#	Time	Username	Problem	Language	Result	Execution time	Memory
379322		Thistle	Split the Attractions (IOI19_split)	C++14	33 / 100	117 ms	16108 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()%5+3;
	int a=rnd()%(n-2)+1;
	int b=rnd()%(n-a-1)+1;
	int c=n-a-b;
	int m=n-1;
	vi v;rep(i,n) v.pb(i);
	shuffle(all(v),rnd);
	vec<int>p,q;
	rep(i,n-1) p.push_back(v[i]),q.pb(v[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);
	}
	int on=0,th=0,tw=0;
	rep(i,n) if(ans[i]==2){
		tw++;
	}
	rep(i,n){
		if(ans[i]==1) on++;
		if(ans[i]==3) th++;
	}
	if(on!=a||th!=c||tw!=b){
				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,1000000){
		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),pa(n,-1);
		auto dfs=[&](int x,int p,auto& dfs)->int{
			sz[x]=1;pa[x]=p;
			for(auto g:f[x]){
				if(g==p) continue;
				sz[x]+=dfs(g,x,dfs);
			}
			return sz[x];
		};dfs(0,-1,dfs);

		int tw=2,twi=b;
		int mn=min({a,b,c}),nxt=b;
		if(a==mn){
			if(b>c) tw=3,twi=c,nxt=c;
		}
		else if(b==mn) {
			if(a<c) tw=1,twi=a,nxt=a;
			else tw=3,twi=c,nxt=c;
		}
		else {
			if(a<b) tw=1,twi=a,nxt=a;
		}

		rep(i,n){
			for(auto g:f[i]){
				if(pa[i]==g) continue;
				if(sz[g]>=min({a,b,c})&&n-sz[g]>=nxt||
						sz[g]>=nxt&&n-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;
					if(sz[g]>=nxt&&n-sz[g]>=min({a,b,c})){
						swap(mn,twi);
						swap(k,tw);
					}

					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==mn) continue;
								used[g]=k;
								q.push(g);
								sum++;
							}
						}
					}
					q.push(i);
					sum=1;
					int d=tw,h=twi;

					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(v[i]),q.pb(v[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:75:2: note: in expansion of macro 'rep'
   75 |  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:2: note: in expansion of macro 'rep'
   78 |  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:85:5: note: in expansion of macro 'rep'
   85 |     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:94:2: note: in expansion of macro 'rep'
   94 |  rep(i,1000000){
      |  ^~~
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:103:2: note: in expansion of macro 'rep'
  103 |  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:107:2: note: in expansion of macro 'rep'
  107 |  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:135:3: note: in expansion of macro 'rep'
  135 |   rep(i,n){
      |   ^~~
split.cpp:138:27: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
  138 |     if(sz[g]>=min({a,b,c})&&n-sz[g]>=nxt||
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:212:3: note: in expansion of macro 'rep'
  212 |   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:216:3: note: in expansion of macro 'rep'
  216 |   rep(i,n) if(used[i]==0){
      |   ^~~

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