oj.uz

답안 #24522

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
24522 2017-06-09T18:20:02 Z rubabredwan CEOI16_icc (CEOI16_icc) C++14
100 / 100
 146 ms 2272 KB 
/* Bismillahir Rahmanir Rahim */
 
#include <bits/stdc++.h>
#include "icc.h"
 
using namespace std;
 
const int N = 105;
 
int n, par[N], mat[N][N];
set<int>comp;
vector<int>nudes[N];
 
int Find(int at){
	return par[at] == at ? at : par[at] = Find(par[at]);
}
 
void Union(int a, int b){
	int x = Find(a);
	int y = Find(b);
	for(auto u : nudes[y]){
		nudes[x].push_back(u);
	}
	par[y] = x;
	comp.erase(y);
}

 
int fuk[N], tt;
 
int get(int sa, int sb, int a[], int b[]){
	int lo = 0, hi = sb - 1;
	while(lo < hi){
		int mid = (lo + hi) / 2; tt = 0;
		for(int i=lo;i<=mid;i++) fuk[tt] = b[i], ++tt;
		if(query(sa, tt, a, fuk)) hi = mid;
		else lo = mid + 1;
	}
	return b[lo];
}
 
int aa[N], bb[N], cr[N];
int sa, sb, sz;
 
void run(int _n){
	n = _n;
	comp.clear();
	for(int i=1;i<=n;i++){
		par[i] = i;
		comp.insert(i);
		nudes[i].push_back(i);
	}
	for(int road = 1; road < n; ++road){
		sz = 0;
		for(auto u : comp) cr[++sz] = u;
		for(int bit = 0; bit <= 7; ++bit){
			sa = 0, sb = 0;
			for(int i = 1; i <= sz; ++i){
				if(i & (1 << bit)) for(auto v : nudes[cr[i]]) aa[sa] = v, ++sa;
				else for(auto v : nudes[cr[i]]) bb[sb] = v, ++sb;
			}
			if(sa == 0 || sb == 0) continue;
			if(query(sa, sb, aa, bb)){
				int x = get(sa, sb, aa, bb);
				int y = get(sb, sa, bb, aa);
				Union(x, y);
				setRoad(x, y);
				break;
			}
		}
	}
}

Subtask #1
7.0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 2132 KB Ok! 98 queries used.
2 Correct 6 ms 2132 KB Ok! 99 queries used.

Subtask #2
11.0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 39 ms 2136 KB Ok! 509 queries used.
2 Correct 43 ms 2132 KB Ok! 639 queries used.
3 Correct 43 ms 2136 KB Ok! 640 queries used.

Subtask #3
22.0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Correct 116 ms 2268 KB Ok! 1399 queries used.
2 Correct 146 ms 2272 KB Ok! 1608 queries used.
3 Correct 129 ms 2268 KB Ok! 1601 queries used.
4 Correct 136 ms 2268 KB Ok! 1513 queries used.

Subtask #4
21.0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Correct 129 ms 2272 KB Ok! 1440 queries used.
2 Correct 126 ms 2264 KB Ok! 1459 queries used.
3 Correct 123 ms 2268 KB Ok! 1566 queries used.
4 Correct 133 ms 2268 KB Ok! 1484 queries used.

Subtask #5
29.0 / 29.0

# 결과 실행 시간 메모리 Grader output
1 Correct 136 ms 2268 KB Ok! 1577 queries used.
2 Correct 136 ms 2264 KB Ok! 1579 queries used.
3 Correct 143 ms 2264 KB Ok! 1616 queries used.
4 Correct 136 ms 2268 KB Ok! 1587 queries used.
5 Correct 123 ms 2264 KB Ok! 1456 queries used.
6 Correct 136 ms 2264 KB Ok! 1537 queries used.

Subtask #6
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 136 ms 2268 KB Ok! 1586 queries used.
2 Correct 139 ms 2268 KB Ok! 1608 queries used.