oj.uz

Submission #52202

# Submission time Handle Problem Language Result Execution time Memory
52202 2018-06-25T04:11:58 Z tmwilliamlin168 ICC (CEOI16_icc) C++14
0 / 100
 7 ms 676 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);
}

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) {
			if(!vis[p[i]]) {
				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[cci])
					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[0][1];
			setRoad(u, v);
			adj[u].push_back(v);
			adj[v].push_back(u);
			break;
		}
		memset(vis, 0, n);
		for(int i=0; i<cci; ++i)
			ccs[i].clear();
		cci=0;
	}
}

Subtask #1
0 / 7.0

# Verdict Execution time Memory Grader output
1 Incorrect 5 ms 376 KB Number of queries more than 3000 out of 1500
2 Halted 0 ms 0 KB -

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 7 ms 376 KB Number of queries more than 5000 out of 2500
2 Halted 0 ms 0 KB -

Subtask #3
0 / 22.0

# Verdict Execution time Memory Grader output
1 Incorrect 7 ms 548 KB Number of queries more than 4500 out of 2250
2 Halted 0 ms 0 KB -

Subtask #4
0 / 21.0

# Verdict Execution time Memory Grader output
1 Incorrect 6 ms 548 KB Number of queries more than 4000 out of 2000
2 Halted 0 ms 0 KB -

Subtask #5
0 / 29.0

# Verdict Execution time Memory Grader output
1 Incorrect 6 ms 548 KB Number of queries more than 3550 out of 1775
2 Halted 0 ms 0 KB -

Subtask #6
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 5 ms 676 KB Number of queries more than 3250 out of 1625
2 Halted 0 ms 0 KB -