oj.uz

Submission #137947

# Submission time Handle Problem Language Result Execution time Memory
137947 2019-07-28T15:16:22 Z darkkcyan ICC (CEOI16_icc) C++14
100 / 100
 150 ms 704 KB 
/*
	- When querying, nodes in connected components must be in the same group or else the query will always return 1
	- Iterate through i and separate connected components into two groups of nodes A and B according to the ith bit of the component's ID
	- Once we find i such that query(A, B) returns 1, we know that the endpoints of the edge have the same bits below i
		- Fix one bit at a time and test if the edge is still there to find the exact bits
	- Since we found A and B such that query(A, B) returns 1, we can binary search for the exact edge
*/

#include <icc.h>
#include <bits/stdc++.h>
using namespace std;

const int mxN=100;
int 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);
}

void run(int n) {
	for(int it=0; it<n-1; ++it) {
		for(int i=0; i<n; ++i) {
			if(!vis[i]) {
				dfs(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;
			int cm=0;
			for(int k=0; k<i; ++k) {
				qa[0].clear();
				qa[1].clear();
				for(int j=0; j<cci; ++j)
					if((j&((1<<(k+1))-1))==cm)
						for(int u : ccs[j])
							qa[j>>i&1].push_back(u+1);
				qr=query(qa[0].size(), qa[1].size(), qa[0].data(), qa[1].data());
				if(!qr)
					cm|=1<<k;
			}
			qa[0].clear();
			qa[1].clear();
			for(int j=0; j<cci; ++j)
				if((j&((1<<i)-1))==cm)
					for(int u : ccs[j])
						qa[j>>i&1].push_back(u+1);
			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();
	}
}

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 504 KB Ok! 97 queries used.
2 Correct 10 ms 504 KB Ok! 99 queries used.

Subtask #2
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 504 KB Ok! 516 queries used.
2 Correct 44 ms 504 KB Ok! 571 queries used.
3 Correct 46 ms 632 KB Ok! 613 queries used.

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 132 ms 504 KB Ok! 1402 queries used.
2 Correct 138 ms 600 KB Ok! 1385 queries used.
3 Correct 138 ms 504 KB Ok! 1463 queries used.
4 Correct 147 ms 596 KB Ok! 1469 queries used.

Subtask #4
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 146 ms 560 KB Ok! 1509 queries used.
2 Correct 139 ms 604 KB Ok! 1456 queries used.
3 Correct 138 ms 504 KB Ok! 1468 queries used.
4 Correct 141 ms 504 KB Ok! 1433 queries used.

Subtask #5
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 150 ms 596 KB Ok! 1549 queries used.
2 Correct 138 ms 632 KB Ok! 1468 queries used.
3 Correct 139 ms 504 KB Ok! 1446 queries used.
4 Correct 137 ms 504 KB Ok! 1468 queries used.
5 Correct 141 ms 632 KB Ok! 1473 queries used.
6 Correct 144 ms 688 KB Ok! 1463 queries used.

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 139 ms 704 KB Ok! 1468 queries used.
2 Correct 138 ms 632 KB Ok! 1468 queries used.