oj.uz

답안 #52205

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
52205 2018-06-25T04:28:02 Z tmwilliamlin168 CEOI16_icc (CEOI16_icc) C++14
90 / 100
 187 ms 1172 KB 
#include <icc.h>
#include <bits/stdc++.h>
using namespace std;

const int mxN=100;
int p[mxN], cci;
bool vis[mxN];
vector<int> adj[mxN], ccs[mxN], qa[2];

void dfs(int u) {
	vis[u]=1;
	ccs[cci].push_back(u);
	for(int v : adj[u])
		if(!vis[v])
			dfs(v);
}

/*
int query(int as, int bs, int *aa, int *ba) {
	cout << "Query " << as << " " << bs << endl;
	for(int i=0; i<as; ++i)
		cout << aa[i] << " ";
	cout << endl;
	for(int i=0; i<bs; ++i)
		cout << ba[i] << " ";
	cout << endl;
	int r;
	cin >> r;
	return r;
}

void setRoad(int u, int v) {
	cout << "Set road " << u << " " << v << endl;
}
//*/

void run(int n) {
	for(int i=0; i<n; ++i)
		p[i]=i;
	random_shuffle(p, p+n);
	for(int it=0; it<n-1; ++it) {
		for(int i=0; i<n; ++i) {
//			cout << "hi1 " << i << endl;
			if(!vis[p[i]]) {
//				cout << "hi2 " << i << endl;
				dfs(p[i]);
				++cci;
			}
		}
		for(int i=0; ; ++i) {
			qa[0].clear();
			qa[1].clear();
			for(int j=0; j<cci; ++j)
				for(int u : ccs[j])
					qa[j>>i&1].push_back(u+1);
			int qr=query(qa[0].size(), qa[1].size(), qa[0].data(), qa[1].data());
			if(!qr)
				continue;
			for(int j=0; j<2; ++j) {
				while(qa[j].size()>1) {
					qr=query(qa[j].size()/2, qa[j^1].size(), qa[j].data(), qa[j^1].data());
					if(qr)
						qa[j].erase(qa[j].begin()+qa[j].size()/2, qa[j].end());
					else
						qa[j].erase(qa[j].begin(), qa[j].begin()+qa[j].size()/2);
				}
			}
			int u=qa[0][0], v=qa[1][0];
			setRoad(u, v);
			adj[u-1].push_back(v-1);
			adj[v-1].push_back(u-1);
			break;
		}
		memset(vis, 0, n);
		while(cci)
			ccs[--cci].clear();
	}
}

/*
int main() {
	int n;
	cin >> n;
	run(n);
}
//*/

Subtask #1
7.0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 9 ms 632 KB Ok! 96 queries used.
2 Correct 10 ms 632 KB Ok! 102 queries used.

Subtask #2
11.0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 40 ms 728 KB Ok! 537 queries used.
2 Correct 63 ms 796 KB Ok! 692 queries used.
3 Correct 58 ms 872 KB Ok! 683 queries used.

Subtask #3
22.0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Correct 137 ms 896 KB Ok! 1455 queries used.
2 Correct 165 ms 896 KB Ok! 1668 queries used.
3 Correct 172 ms 896 KB Ok! 1468 queries used.
4 Correct 144 ms 1056 KB Ok! 1516 queries used.

Subtask #4
21.0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Correct 135 ms 1056 KB Ok! 1478 queries used.
2 Correct 135 ms 1056 KB Ok! 1490 queries used.
3 Correct 168 ms 1056 KB Ok! 1653 queries used.
4 Correct 132 ms 1056 KB Ok! 1436 queries used.

Subtask #5
29.0 / 29.0

# 결과 실행 시간 메모리 Grader output
1 Correct 152 ms 1056 KB Ok! 1620 queries used.
2 Correct 169 ms 1056 KB Ok! 1651 queries used.
3 Correct 187 ms 1056 KB Ok! 1672 queries used.
4 Correct 164 ms 1160 KB Ok! 1614 queries used.
5 Correct 147 ms 1160 KB Ok! 1513 queries used.
6 Correct 160 ms 1160 KB Ok! 1577 queries used.

Subtask #6
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 178 ms 1172 KB Too many queries! 1642 out of 1625
2 Halted 0 ms 0 KB -