oj.uz

Submission #605238

# Submission time Handle Problem Language Result Execution time Memory
605238 2022-07-25T14:30:48 Z sentheta ICC (CEOI16_icc) C++17
100 / 100
 141 ms 616 KB 
#include"icc.h"
#include<algorithm>
#include<iostream>
#include<cassert>
#include<string>
#include<vector>
#include<stack>
#include<queue>
#include<map>
#include<set>
using namespace std;
 
#define Int long long
#define V vector
#define all(x) (x).begin(), (x).end()
#define rep(i,a,b) for(int i=(int)(a); i<(int)(b); i++)
#define dbg(x) cout << "?" << #x << " : " << x << endl; cout.flush();
 
int qry(V<int> a,V<int> b){
	return query(a.size(), b.size(), &a[0], &b[0]);
}
 
const int N = 105;
 
int n;
 
 
V<int> v[N];
int p[N];
int find(int x){
	if(p[x]==x) return x;
	return p[x] = find(p[x]);
}
bool same(int x,int y){
	return find(x)==find(y);
}
bool unite(int x,int y){
	if((x=find(x))==(y=find(y))) return 0;
 
	for(int i : v[y]) v[x].push_back(i);
	p[y] = x;
	return 1;
}
 
 
void solve(){
 
	// Find possible ccs
	V<int> leads;
	rep(i,1,n+1) if(find(i)==i){
		leads.push_back(i);
	}
	random_shuffle(all(leads));
 
	rep(b,0,7){
		// split into two groups
		V<int> g[2];
		rep(i,0,leads.size()){
			for(int j : v[leads[i]]){
				g[i>>b&1].push_back(j);
			}
		}
		
 
		if(!qry(g[0], g[1])) continue;
		// from here, the answer is between g[0] and g[1]
 
		//for(int i : g[0]) cout << i << " ";
		//cout << endl;
		//for(int i : g[1]) cout << i << " ";
		//cout << endl;
 
		// pinpoint exact node
		rep(i,0,2){
			while(g[i].size() > 1){
				V<int> sg[2];
				rep(j,0,g[i].size()){
					sg[j&1].push_back(g[i][j]);
				}
 
				if(qry(sg[0], g[i^1])){
					g[i] = sg[0];
				}
				else g[i] = sg[1];
			}
			assert(g[i].size()==1);
		}
 
		int p = g[0][0], q = g[1][0];
		//dbg(p); dbg(q);
		unite(p, q);
		setRoad(p, q);
		return;
	}
	assert(0);
 
	
}
 
 
 
void run(int _n){
	n = _n;
	rep(i,0,N){
		v[i] = {i};
		p[i] = i;
	}
 
	rep(i,0,n-1){
		solve();
	}
 
	return;
	//query(1, 2, {1}, {2,3});
	//setRoad(1, 2);
}

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 468 KB Ok! 104 queries used.
2 Correct 4 ms 496 KB Ok! 101 queries used.

Subtask #2
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 384 KB Ok! 518 queries used.
2 Correct 34 ms 468 KB Ok! 652 queries used.
3 Correct 32 ms 492 KB Ok! 644 queries used.

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 95 ms 496 KB Ok! 1400 queries used.
2 Correct 141 ms 492 KB Ok! 1603 queries used.
3 Correct 101 ms 496 KB Ok! 1428 queries used.
4 Correct 99 ms 504 KB Ok! 1487 queries used.

Subtask #4
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 95 ms 504 KB Ok! 1452 queries used.
2 Correct 103 ms 500 KB Ok! 1473 queries used.
3 Correct 129 ms 500 KB Ok! 1588 queries used.
4 Correct 94 ms 488 KB Ok! 1421 queries used.

Subtask #5
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 106 ms 504 KB Ok! 1582 queries used.
2 Correct 108 ms 496 KB Ok! 1572 queries used.
3 Correct 117 ms 500 KB Ok! 1593 queries used.
4 Correct 113 ms 500 KB Ok! 1583 queries used.
5 Correct 98 ms 496 KB Ok! 1469 queries used.
6 Correct 103 ms 496 KB Ok! 1524 queries used.

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 111 ms 616 KB Ok! 1596 queries used.
2 Correct 110 ms 492 KB Ok! 1594 queries used.