oj.uz

Submission #113739

# Submission time Handle Problem Language Result Execution time Memory
113739 2019-05-28T06:48:46 Z MAMBA ICC (CEOI16_icc) C++17
100 / 100
 169 ms 664 KB 
#include "icc.h"
#include <bits/stdc++.h> 

using namespace std;

#define rep(i , j , k) for(int i = j ; i < (int)k; i++)
#define pb push_back

constexpr int N = 110;

int sz[N], par[N];
vector<int> h[N];
set<int> st;

int getPar(int v) {
	if (par[v] == -1) return v;
	return getPar(par[v]);
}

inline void merge(int u , int v) {
	v = getPar(v);
	u = getPar(u);

	if (sz[v] > sz[u]) swap(v , u);

	for (auto e : h[v])
		h[u].pb(e);
	h[v].clear();
	par[v] = u;
	sz[u] += sz[v];
	st.erase(v);
}

int a[N], b[N];

unordered_map<int , int> mp , arr;
int ptr;
inline void solve() {
	ptr = 0;
	mp.clear();
	arr.clear();
	for (auto e : st) {
		arr[ptr] = e;
		mp[e] = ptr++;
	}	
	int xor_ = 0;
	for (int i = 0; (1 << i) <= ptr; i++) {
		int size_a = 0;
		int size_b = 0;
		rep(j , 0 , ptr) {
			if ((j >> i) & 1) {
				for (auto e : h[arr[j]])
					a[size_a++] = e;
			}
			else {
				for (auto e : h[arr[j]])
					b[size_b++] = e;
			}
		}
		xor_ |= (query(size_a , size_b , a , b) ? (1 << i) : 0);
	}
	int now_a = 0 , now_b = 0;
	now_b |= 1 << __builtin_ctz(xor_);
	for (int i = 0; (1 << i) <= ptr; i++) {
		if (now_b & (1 << i)) continue;
		if ((xor_ >> i) & 1) {
			int size_a = 0;
			int size_b = 0;
			rep(j , 0 , ptr) {
				int must = ((1 << __builtin_ctz(xor_)) | ((1 << i) - 1));
				if ((j & must) == now_a) {
					if ((j >> i) & 1) 
						for (auto e : h[arr[j]])
							a[size_a++] = e;
				}
				else if ((j & must) == now_b) {
					if ((j >> i) & 1) ;
					else 
						for (auto e: h[arr[j]])
							b[size_b++] = e;
				}
			}
			if (query(size_a , size_b , a , b))
				now_a += (1 << i);
			else
				now_b += (1 << i);
		}
		else {
			int size_a = 0;
			int size_b = 0;
			rep(j , 0 , ptr) {
				int must = ((1 << __builtin_ctz(xor_)) | ((1 << i) - 1));
				if ((j & must) == now_a) {
					if ((j >> i) & 1) 
						for (auto e : h[arr[j]])
							a[size_a++] = e;
				}
				else if ((j & must) == now_b) {
					if ((j >> i) & 1) 
						for (auto e : h[arr[j]])
							b[size_b++] = e;
				}
			}
			if (query(size_a , size_b , a , b)) {
				now_a += (1 << i);
				now_b += (1 << i);
			}
		}
	}

	now_a = arr[now_a];
	now_b = arr[now_b];
	int lo = 0,  hi = h[now_a].size();
	while (lo != hi - 1) {
		int mid = lo + hi >> 1;
		int size_a = 0;
		int size_b = 0;
		rep(i , 0 , mid)
			a[size_a++] = h[now_a][i];
		for (auto e : h[now_b])
			b[size_b++] = e;
		if (query(size_a , size_b , a , b))
			hi = mid;
		else lo = mid;
	}

	int man = lo;

	lo = 0, hi = h[now_b].size();
	while (lo != hi - 1) {
		int mid = lo + hi >> 1;
		a[0] = h[now_a][man];
		rep(i , 0 , mid)
			b[i] = h[now_b][i];
		if (query(1 , mid , a , b))
			hi = mid;
		else
			lo = mid;
	}
	setRoad(h[now_a][man] , h[now_b][lo]);
	merge(h[now_a][man] , h[now_b][lo]);
}

void run(int n) {
  memset(par , -1, sizeof(par));
  rep(i, 1 , n + 1) {
    h[i].pb(i);
  	sz[i] = 1;	
  }
	rep(i , 1 , n + 1)
		st.insert(i);
	rep(i , 0 , n) 
		solve();
}

Compilation message

icc.cpp: In function 'void solve()':
icc.cpp:115:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   int mid = lo + hi >> 1;
             ~~~^~~~
icc.cpp:131:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   int mid = lo + hi >> 1;
             ~~~^~~~

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 512 KB Ok! 123 queries used.
2 Correct 9 ms 536 KB Ok! 123 queries used.

Subtask #2
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 512 KB Ok! 662 queries used.
2 Correct 41 ms 572 KB Ok! 648 queries used.
3 Correct 41 ms 632 KB Ok! 659 queries used.

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 134 ms 512 KB Ok! 1625 queries used.
2 Correct 119 ms 580 KB Ok! 1625 queries used.
3 Correct 137 ms 512 KB Ok! 1625 queries used.
4 Correct 135 ms 632 KB Ok! 1620 queries used.

Subtask #4
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 131 ms 664 KB Ok! 1609 queries used.
2 Correct 134 ms 632 KB Ok! 1610 queries used.
3 Correct 118 ms 512 KB Ok! 1625 queries used.
4 Correct 135 ms 612 KB Ok! 1621 queries used.

Subtask #5
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 126 ms 572 KB Ok! 1620 queries used.
2 Correct 122 ms 632 KB Ok! 1625 queries used.
3 Correct 132 ms 572 KB Ok! 1625 queries used.
4 Correct 129 ms 632 KB Ok! 1625 queries used.
5 Correct 136 ms 588 KB Ok! 1625 queries used.
6 Correct 136 ms 512 KB Ok! 1625 queries used.

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 169 ms 584 KB Ok! 1625 queries used.
2 Correct 130 ms 512 KB Ok! 1625 queries used.