oj.uz

Submission #95176

# Submission time Handle Problem Language Result Execution time Memory
95176 2019-01-27T21:35:47 Z jasony123123 ICC (CEOI16_icc) C++11
100 / 100
 136 ms 632 KB 
#define _CRT_SECURE_NO_WARNINGS
#include <bits/stdc++.h>
#include "icc.h"
//#include <ext/pb_ds/tree_policy.hpp>
//#include <ext/pb_ds/assoc_container.hpp>
using namespace std;
//using namespace __gnu_pbds;

#define FOR(i,start,end) for(int i=start;i<(int)(end);i++)
#define FORE(i,start,end) for(int i=start;i<=(int)end;i++)
#define RFOR(i,start,end) for(int i = start; i>end; i--)
#define RFORE(i,start,end) for(int i = start; i>=end; i--)
#define all(a) a.begin(), a.end()
#define mt make_tuple
#define mp make_pair
#define v vector
#define sf scanf
#define pf printf
#define dvar(x) cout << #x << " := " << x << "\n"
#define darr(x,n) FOR(i,0,n) cout << #x << "[" << i << "]" << " := " << x[i] << "\n"

typedef long long ll;
typedef long double ld;
typedef pair<int, int > pii;
typedef pair<ll, ll> pll;
//template <class T> using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
template<class T> void minn(T &a, T b) { a = min(a, b); }
template<class T> void maxx(T &a, T b) { a = max(a, b); }

void io() {
#ifdef LOCAL_PROJECT 
	freopen("input.in", "r", stdin); freopen("output.out", "w", stdout);
#else 

#endif 
	ios_base::sync_with_stdio(false); cin.tie(NULL);
}

const ll MOD = 1000000007LL;
const ll PRIME = 105943LL;
const ll INF = 1e18;
/******************************CEOI 2016 Day 1 P1 - ICC*********************************/

v<int> adj[101];
v<v<int>> comp;
int N, M;

v<int> unpack(v<int> &compA) {
	v<int> nodeA;
	for (auto c : compA) for (auto x : comp[c])
		nodeA.push_back(x);
	return nodeA;
}

int queryNodes(v<int> nodeA, v<int> nodeB) {
	return query(nodeA.size(), nodeB.size(), nodeA.data(), nodeB.data());
}

int queryComp(v<int> &compA, v<int> &compB) {
	return queryNodes(unpack(compA), unpack(compB));
}


void dfs(int x, v<bool> &vis, v<int> &rec) {
	if (vis[x]) return;
	vis[x] = 1;
	rec.push_back(x);
	for (auto c : adj[x]) dfs(c, vis, rec);
}

void updComp() {
	v<bool> vis(N + 1, 0);
	comp.clear();
	FORE(i, 1, N) if (!vis[i]) {
		comp.push_back(v<int>());
		dfs(i, vis, comp.back());
	}
	M = comp.size();
}

void findConnectComp(v<int> &compA, v<int> &compB) {
	FOR(b, 0, 8) {
		v<int> ca, cb;
		FOR(i, 0, M) {
			if (i&(1 << b)) ca.push_back(i);
			else cb.push_back(i);
		}
		if (!ca.empty() && !cb.empty() && queryComp(ca, cb)) {
			compA = ca, compB = cb;
			return;
		}
	}
}

void reduce(v<int> &noa, v<int> &nob) {
	while (nob.size() > 1) {
		v<int> top, bot;
		int mid = (0 + nob.size() - 1) / 2;
		FORE(i, 0, mid)
			top.push_back(nob[i]);
		FORE(i, mid + 1, nob.size() - 1)
			bot.push_back(nob[i]);

		if (queryNodes(noa, top))
			nob = top;
		else
			nob = bot;
	}
}

void run(int n) {
	N = n;
	FOR(r, 0, n - 1) {
		updComp();

		v<int> compA, compB;
		findConnectComp(compA, compB);

		v<int> nodeA = unpack(compA);
		v<int> nodeB = unpack(compB);
		reduce(nodeA, nodeB);
		reduce(nodeB, nodeA);

		setRoad(nodeA[0], nodeB[0]);
		adj[nodeA[0]].push_back(nodeB[0]);
		adj[nodeB[0]].push_back(nodeA[0]);
	}
}

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 504 KB Ok! 95 queries used.
2 Correct 8 ms 504 KB Ok! 96 queries used.

Subtask #2
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 504 KB Ok! 530 queries used.
2 Correct 43 ms 560 KB Ok! 647 queries used.
3 Correct 43 ms 504 KB Ok! 647 queries used.

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 104 ms 560 KB Ok! 1350 queries used.
2 Correct 134 ms 564 KB Ok! 1595 queries used.
3 Correct 124 ms 560 KB Ok! 1594 queries used.
4 Correct 124 ms 504 KB Ok! 1496 queries used.

Subtask #4
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 113 ms 508 KB Ok! 1462 queries used.
2 Correct 115 ms 568 KB Ok! 1411 queries used.
3 Correct 117 ms 600 KB Ok! 1551 queries used.
4 Correct 109 ms 604 KB Ok! 1390 queries used.

Subtask #5
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 122 ms 632 KB Ok! 1546 queries used.
2 Correct 126 ms 604 KB Ok! 1580 queries used.
3 Correct 136 ms 504 KB Ok! 1622 queries used.
4 Correct 123 ms 528 KB Ok! 1539 queries used.
5 Correct 113 ms 504 KB Ok! 1420 queries used.
6 Correct 123 ms 604 KB Ok! 1517 queries used.

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 127 ms 564 KB Ok! 1591 queries used.
2 Correct 130 ms 504 KB Ok! 1604 queries used.