oj.uz

Submission #605850

# Submission time Handle Problem Language Result Execution time Memory
605850 2022-07-26T03:42:21 Z sentheta ICC (CEOI16_icc) C++17
100 / 100
 128 ms 512 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 4 ms 468 KB Ok! 96 queries used.
2 Correct 5 ms 468 KB Ok! 101 queries used.

Subtask #2
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 468 KB Ok! 529 queries used.
2 Correct 35 ms 468 KB Ok! 658 queries used.
3 Correct 31 ms 508 KB Ok! 630 queries used.

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 87 ms 504 KB Ok! 1363 queries used.
2 Correct 108 ms 484 KB Ok! 1577 queries used.
3 Correct 84 ms 484 KB Ok! 1337 queries used.
4 Correct 95 ms 480 KB Ok! 1474 queries used.

Subtask #4
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 94 ms 468 KB Ok! 1490 queries used.
2 Correct 101 ms 500 KB Ok! 1465 queries used.
3 Correct 99 ms 468 KB Ok! 1560 queries used.
4 Correct 109 ms 484 KB Ok! 1423 queries used.

Subtask #5
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 128 ms 492 KB Ok! 1589 queries used.
2 Correct 121 ms 500 KB Ok! 1564 queries used.
3 Correct 113 ms 512 KB Ok! 1589 queries used.
4 Correct 108 ms 488 KB Ok! 1526 queries used.
5 Correct 108 ms 468 KB Ok! 1492 queries used.
6 Correct 96 ms 468 KB Ok! 1525 queries used.

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 105 ms 500 KB Ok! 1571 queries used.
2 Correct 106 ms 496 KB Ok! 1581 queries used.