제출 #758342

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
758342		jamezzz	ICC (CEOI16_icc)	C++17	10 / 100	130 ms	608 KiB

icc

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

#define sf scanf
#define pf printf
#define fi first
#define se second
#define pb push_back
#define sz(x) ((int)x.size())
#define all(x) x.begin(),x.end()
typedef pair<int,int> ii;

#define maxn 105

int a[maxn],b[maxn],par[maxn],in[maxn];

int fp(int i){return par[i]==i?i:par[i]=fp(par[i]);}
void join(int x,int y){
	x=fp(x),y=fp(y);
	par[x]=y;
}

vector<int> fill(vector<int> &x){
	for(int i:x)in[i]=1;
	vector<int> res;
	for(int i=1;par[i]!=0;++i){
		if(in[fp(i)])res.pb(i);
	}
	for(int i:x)in[i]=0;
	return res;
}

int ask(vector<int> x,vector<int> y){
	if(x.empty()||y.empty())return 0;
	for(int i=0;i<sz(x);++i)a[i]=x[i];
	for(int i=0;i<sz(y);++i)b[i]=y[i];
	return query(sz(x),sz(y),a,b);
}

int dnc(vector<int> &x,vector<int> &y){
	if(x.size()==1)return x[0];
	vector<int> l,r;
	for(int i=0;i<sz(x);++i){
		if(i<sz(x)/2)l.pb(x[i]);
		else r.pb(x[i]);
	}
	if(ask(l,y))return dnc(l,y);
	else return dnc(r,y);
}

void run(int N){
	for(int i=1;i<=N;++i)par[i]=i;
	for(int _=0;_<N-1;++_){
		int curx=0,cury=0;
		vector<int> v;
		for(int i=1;i<=N;++i){
			if(fp(i)==i)v.pb(i);
		}
		vector<int> same;
		for(int i=1;i<sz(v);i<<=1){
			vector<int> l,r;
			for(int x=0;x<sz(v);++x){
				if(x&i)r.pb(v[x]);
				else l.pb(v[x]);
			}
			int res=ask(fill(l),fill(r));
			if(res==0){//they are from the same set
				same.pb(i);
			}
			else{//they are from different sets
				vector<int> l,r;
				int msk=curx|cury;
				for(int x=0;x<sz(v);++x){
					if((msk&x)==curx&&(x&i))l.pb(v[x]);
					else if((msk&x)==cury&&!(x&i))r.pb(v[x]);
				}
				if(ask(fill(l),fill(r)))curx^=i;
				else cury^=i;
			}
		}
		int msk=curx|cury;
		for(int i:same){
			vector<int> l,r;
			for(int x=0;x<sz(v);++x){
				if((msk&x)==curx&&(x&i))l.pb(v[x]);
				else if((msk&x)==cury&&(x&i))r.pb(v[x]);
			}
			if(ask(fill(l),fill(r)))curx^=i,cury^=i;
		}
		vector<int> l,r;
		for(int i=1;i<=N;++i){
			if(fp(i)==v[curx])l.pb(i);
			else if(fp(i)==v[cury])r.pb(i);
		}
		int x=dnc(l,r),y=dnc(r,l);
		setRoad(x,y);
		join(x,y);
	}
}

#ifdef DEBUG
int num_qry;
vector<ii> EL,tmp;
int query(int size_a,int size_b,int a[],int b[]){
	++num_qry;
	for(int i=0;i<size_a;++i){
		for(int j=0;j<size_b;++j){
			int x=a[i],y=b[j];
			for(auto[a,b]:EL){
				if((a==x&&b==y)||(b==x&&a==y))return 1;
			}
		}
	}
	return 0;
}
void setRoad(int a,int b){
	pf("answer: %d %d\n",a,b);
	auto[c,d]=EL.back();
	assert((a==c&&b==d)||(a==d&&b==c));
	if(!tmp.empty()){
		EL.pb(tmp.back());
		pf("curedge: %d %d\n",EL.back().fi,EL.back().se);
		tmp.pop_back();
	}
}
int main(){
	int n;sf("%d",&n);
	for(int i=0;i<n-1;++i){
		int a,b;sf("%d%d",&a,&b);
		tmp.pb({a,b});
	}
	reverse(all(tmp));
	EL.pb(tmp.back());
	pf("curedge: %d %d\n",EL.back().fi,EL.back().se);
	tmp.pop_back();
	run(n);
	assert(tmp.empty());
	pf("AC\n");
}
#endif

/*

*/

• Subtask 1: 0 / 7
• Subtask 2: 0 / 11
• Subtask 3: 0 / 22
• Subtask 4: 0 / 21
• Subtask 5: 0 / 29
• Subtask 6: 10 / 10