제출 #61708

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
61708		khohko	ICC (CEOI16_icc)	C++17	0 / 100	2086 ms	63444 KiB

icc

#include "icc.h"
#include<bits/stdc++.h>
using namespace std;
#define ll int
#define fr first
#define sc second
#define pb push_back
#define ARRS ((ll)(2e6+100))
#define MAX ((ll)(2e9+100))

ll a[ARRS];
ll b[ARRS];
ll c[ARRS];
ll ca,cb;

ll pr[ARRS];
ll f[200][200];
vector<ll> v[ARRS];

ll par(ll x){
	if(x==pr[x])return x;
	else return pr[x]=par(pr[x]);
}

void join(ll x,ll y){
	x=par(x);
	y=par(y);
	if(x==y)return;
	pr[y]=x;
	for(auto k:v[y])v[x].pb(k);
}

//void setRoad(ll a,ll b){
//	cout<<"------"<<endl;
//	cout<<"PAS:"<<a<<" "<<b<<endl;
//	cout<<endl;
//}
//ll query(ll n,ll m,ll *a,ll *b){
//	cout<<n<<endl;
//	for(int i=0; i<n; i++)cout<<a[i]<<" \n"[i==n-1];
//	cout<<m<<endl;
//	for(int i=0; i<m; i++)cout<<b[i]<<" \n"[i==m-1];
//	cout<<"????\n";
//	ll k;
//	cin>>k;
//	cout<<endl;
//	return k;
//}

vector<pair<vector<ll>,vector<ll> > > d;

void run(int n){
	for(int i=1; i<=n; i++){
		pr[i]=i;
		v[i].pb(i);
	}
	vector<ll> va,vb;
	for(int q=0; q<n-1; q++){
		ll ct=0;
		for(int i=1; i<=n; i++){
			for(int j=1; j<=n; j++){
				if(par(i)==par(j))f[i][j]=0;
				else {
					f[i][j]=1;
					if(i<j)ct++;
				}
			}
		}


		while(ct>1){
			ll t=0;
			va.clear();
			vb.clear();
			ca=0;
			cb=0;
			vector<pair<ll,ll> > ge;

			for(int i=1; i<=n; i++){
				if(i==par(i)){
					ge.pb({i,rand()%2});
				}
			}
			random_shuffle(ge.begin(),ge.end());

			for(auto r:ge){
				ll i=r.fr;
				if(r.sc){
					swap(va,vb);
					swap(ca,cb);
					swap(a,b);
				}
				for(auto x:v[i]){
					ll e=0;
					for(int i=1; i<=n; i++)
						if(f[x][i])e=1;
					if(!e)continue;
					for(auto y:vb)
						if(f[x][y])f[x][y]=f[y][x]=2,t++;
					va.pb(x);
					a[ca++]=x;
//					cout<<x<<" "<<t<<" "<<ct<<endl;
					if(t==ct){
						va.pop_back();
						ca--;
						for(auto y:vb)
							if(f[x][y])f[x][y]=1,f[y][x]=1,t--;
						break;
					}
					if(t>=ct/2)break;
				}

			}
//			cout<<"->"<<t<<endl;
			ct=0;
			if(query(ca,cb,a,b)){
				for(int i=1; i<=n; i++){
					for(int j=1; j<=n; j++){
						if(f[i][j]==2)ct+=i<j,f[i][j]=1;
						else f[i][j]=0;
					}
				}
			}
			else {
				for(int i=1; i<=n; i++){
					for(int j=1; j<=n; j++){
						if(f[i][j]==1)ct+=i<j,f[i][j]=1;
						else f[i][j]=0;
					}
				}
			}
		}

		for(int i=1; i<=n; i++)
			for(int j=1; j<=n; j++)
				if(f[i][j]&&i<j){join(i,j);setRoad(i,j);}
	}


}

//int main(){
//	run(5);
//
//
//}

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