oj.uz

Submission #758345

# Submission time Handle Problem Language Result Execution time Memory
758345 2023-06-14T13:26:06 Z jamezzz ICC (CEOI16_icc) C++17
100 / 100
 119 ms 612 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){
	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);
		}
		//for(int i:v)pf("%d ",i);pf("\n");
		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;
			}
		}
		//pf("%d %d\n",curx,cury);
		for(int i:same){
			int msk=curx|cury;
			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;
			//pf("i %d: %d %d\n",i,curx,cury);
		}
		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
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 592 KB Ok! 128 queries used.
2 Correct 5 ms 468 KB Ok! 120 queries used.

Subtask #2
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 500 KB Ok! 670 queries used.
2 Correct 38 ms 468 KB Ok! 646 queries used.
3 Correct 34 ms 480 KB Ok! 648 queries used.

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 113 ms 488 KB Ok! 1683 queries used.
2 Correct 105 ms 500 KB Ok! 1592 queries used.
3 Correct 117 ms 612 KB Ok! 1630 queries used.
4 Correct 111 ms 480 KB Ok! 1648 queries used.

Subtask #4
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 108 ms 468 KB Ok! 1614 queries used.
2 Correct 109 ms 480 KB Ok! 1625 queries used.
3 Correct 102 ms 484 KB Ok! 1592 queries used.
4 Correct 107 ms 500 KB Ok! 1642 queries used.

Subtask #5
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 102 ms 480 KB Ok! 1601 queries used.
2 Correct 110 ms 468 KB Ok! 1597 queries used.
3 Correct 114 ms 488 KB Ok! 1605 queries used.
4 Correct 109 ms 468 KB Ok! 1625 queries used.
5 Correct 108 ms 468 KB Ok! 1668 queries used.
6 Correct 108 ms 496 KB Ok! 1649 queries used.

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 119 ms 588 KB Ok! 1597 queries used.
2 Correct 106 ms 480 KB Ok! 1592 queries used.