oj.uz

Submission #61706

# Submission time Handle Problem Language Result Execution time Memory
61706 2018-07-26T11:31:25 Z khohko ICC (CEOI16_icc) C++17
7 / 100
 2000 ms 63564 KB 
#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;
//			cout<<ct<<endl;
//			for(int i=1; i<=n; i++){
//				for(int j=1; j<=n; j++){
//					cout<<f[i][j]<<" ";
//				}
//				cout<<endl;
//			}
//			cout<<endl;
			vector<pair<ll,ll> > ge;

			for(int i=1; i<=n; i++){
				if(i==par(i)){
					c[i]=0;
					for(auto x:v[i]){
						for(int j=1; j<=n; j++)
							c[i]+=f[x][j];
					}
					ge.pb({c[i],i});
				}
			}
			//sort(ge.begin(),ge.end());
			//reverse(ge.begin(),ge.end());
			random_shuffle(ge.begin(),ge.end());

			for(auto r:ge){
				ll i=r.sc;
				if(va.size()>vb.size()){
					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
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1099 ms 63204 KB Ok! 145 queries used.
2 Correct 1159 ms 63496 KB Ok! 131 queries used.

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2052 ms 63496 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 22.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2054 ms 63500 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 21.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2057 ms 63564 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
0 / 29.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2071 ms 63564 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #6
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2062 ms 63564 KB Time limit exceeded
2 Halted 0 ms 0 KB -