oj.uz

Submission #61408

# Submission time Handle Problem Language Result Execution time Memory
61408 2018-07-25T19:46:08 Z khohko ICC (CEOI16_icc) C++17
61 / 100
 292 ms 47936 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 ca,cb;

ll pr[ARRS];
ll f[ARRS];
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;
}

//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;
//}



void run(int n){
	for(int i=1; i<=n; i++){
		pr[i]=i;
		v[i].pb(i);
	}

	vector<ll> va,vb;
	for(int i=0; i<n-1; i++){
		do{
			for(int i=1; i<=n; i++)
				f[i]=0;
			ca=cb=0;
			for(int i=1; i<=n; i++){
				if(!f[par(i)])
					f[par(i)]=rand()%2+1;
				if(f[par(i)]==1)a[ca++]=i;
				else b[cb++]=i;
			}
		}
		while(!query(ca,cb,a,b));

		va.clear();
		vb.clear();
		for(int i=1; i<=n; i++){
			//if(i==par(i)){
			if(f[par(i)]==1)va.pb(i);
			else vb.pb(i);
			//}
		}
		ll l=1,r=va.size();
		while(l<r){
			ll m=l+r>>1;
			ca=0;
			for(int i=0; i<m; i++){
				//for(auto k:v[va[i]])
				a[ca++]=va[i];
			}
			if(query(ca,cb,a,b))
				r=m;
			else l=m+1;
		}
		ca=1;
		ll x=va[l-1];
		a[0]=x;
		l=1,r=vb.size();
		while(l<r){
			ll m=l+r>>1;
			cb=0;
			for(int i=0; i<m; i++){
				//for(auto k:v[vb[i]])
				b[cb++]=vb[i];
			}
			if(query(ca,cb,a,b))
				r=m;
			else l=m+1;
		}
		ll y=vb[l-1];
		setRoad(x,y);
		join(x,y);
	}

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

Compilation message

icc.cpp: In function 'void run(int)':
icc.cpp:81:10: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
    ll m=l+r>>1;
         ~^~
icc.cpp:96:10: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
    ll m=l+r>>1;
         ~^~

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 50 ms 47480 KB Ok! 101 queries used.
2 Correct 63 ms 47660 KB Ok! 104 queries used.

Subtask #2
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 114 ms 47792 KB Ok! 558 queries used.
2 Correct 106 ms 47792 KB Ok! 855 queries used.
3 Correct 153 ms 47792 KB Ok! 815 queries used.

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 195 ms 47792 KB Ok! 1488 queries used.
2 Correct 292 ms 47792 KB Ok! 2128 queries used.
3 Correct 229 ms 47792 KB Ok! 1638 queries used.
4 Correct 238 ms 47792 KB Ok! 1711 queries used.

Subtask #4
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 261 ms 47884 KB Ok! 1721 queries used.
2 Correct 232 ms 47884 KB Ok! 1672 queries used.
3 Correct 250 ms 47936 KB Ok! 1845 queries used.
4 Correct 201 ms 47936 KB Ok! 1572 queries used.

Subtask #5
0 / 29.0

# Verdict Execution time Memory Grader output
1 Incorrect 277 ms 47936 KB Too many queries! 1869 out of 1775
2 Halted 0 ms 0 KB -

Subtask #6
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 266 ms 47936 KB Too many queries! 1923 out of 1625
2 Halted 0 ms 0 KB -