oj.uz

답안 #758288

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
758288 2023-06-14T12:03:39 Z jamezzz CEOI16_icc (CEOI16_icc) C++17
0 / 100
 21 ms 588 KB 
#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){
	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;
				for(int x=0;x<sz(v);++x){
					if((curx&x)==curx&&(x&i))l.pb(v[x]);
					else if((cury&x)==cury&&!(x&i))r.pb(v[x]);
				}
				if(ask(l,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: %d\n",num_qry);
}
#endif

/*
4
2 4
1 3
1 4

15
9 10
10 11
11 12
12 13
13 14
14 15
1 2
2 3
3 4
4 5
5 6
6 7
7 8
8 9

5
3 4
4 5
1 2
2 3
*/

Subtask #1
0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 7 ms 468 KB Ok! 127 queries used.
2 Incorrect 1 ms 468 KB Wrong road!
3 Halted 0 ms 0 KB -

Subtask #2
0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 3 ms 468 KB Wrong road!
2 Halted 0 ms 0 KB -

Subtask #3
0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 4 ms 496 KB Wrong road!
2 Halted 0 ms 0 KB -

Subtask #4
0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 3 ms 468 KB Wrong road!
2 Halted 0 ms 0 KB -

Subtask #5
0 / 29.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 12 ms 588 KB Wrong road!
2 Halted 0 ms 0 KB -

Subtask #6
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 21 ms 536 KB Wrong road!
2 Halted 0 ms 0 KB -