oj.uz

Submission #882372

# Submission time Handle Problem Language Result Execution time Memory
882372 2023-12-03T05:45:09 Z ono_de206 ICC (CEOI16_icc) C++14
100 / 100
 89 ms 872 KB 
#include "icc.h"
#include <bits/stdc++.h>
using namespace std;

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

#define in insert
#define all(x) x.begin(),x.end()
#define pb push_back
#define eb emplace_back
#define ff first
#define ss second

//#define int long long

typedef long long ll;
typedef vector<int> vi;
typedef set<int> si;
typedef multiset<int> msi;
typedef pair<int, int> pii;
typedef vector<pii> vpii;

const int mxn = 110;
int A[mxn], B[mxn], n, par[mxn];
vector<int> g[mxn], all;

int get(int x) {
	if(par[x] == x) return x;
	return par[x] = get(par[x]);
}

void merge(int x, int y) {
	x = get(x);
	y = get(y);
	if(g[x].size() < g[y].size()) swap(x, y);
	all.erase(find(all(all), y));
	g[x].insert(g[x].end(), all(g[y]));
	par[y] = x;
	g[y].clear();
}

int ask(vector<int> a, vector<int> b) {
	int sza = 0, szb = 0;
	for(int x : a) {
		for(int y : g[x]) {
			A[sza++] = y;
		}
	}
	for(int x : b) {
		for(int y : g[x]) {
			B[szb++] = y;
		}
	}
	return query(sza, szb, A, B);
}

pair<int, int> find(vector<int> x, vector<int> y) {
	pair<int, int> ret{0, 0};
	int A[n + 1], B[n + 1];
	int sza, szb = 0;
	int l = -1, r = (int)x.size() - 1;
	for(int p : y) {
		B[szb++] = p;
	}
	while(r - l > 1) {
		int m = (l + r) / 2;
		sza = 0;
		for(int i = 0; i <= m; i++) {
			A[sza++] = x[i];
		}
		if(query(sza, szb, A, B)) r = m;
		else l = m;
	}
	ret.ff = x[r];

	sza = 0;
	l = -1, r = (int)y.size() - 1;
	for(int p : x) {
		A[sza++] = p;
	}
	while(r - l > 1) {
		int m = (l + r) / 2;
		szb = 0;
		for(int i = 0; i <= m; i++) {
			B[szb++] = y[i];
		}
		if(query(sza, szb, A, B)) r = m;
		else l = m;
	}
	ret.ss = y[r];
	return ret;
}

void run(int _n) {
	n = _n;
	for(int i = 1; i <= n; i++) {
		g[i].pb(i);
		all.pb(i);
		par[i] = i;
	}
	for(int t = 1; t < n; t++) {
		int sz = (int)all.size();
		while(sz & (sz - 1)) {
			sz++;
			all.pb(-1);
		}

		for(int j = 2; j <= sz; j *= 2) {
			int lol = sz / j;
			vector<int> a, b;
			for(int k = 1; k <= j; k++) {
				for(int p = lol * (k - 1); p < lol * k; p++) {
					if(all[p] != -1) {
						if(k % 2) a.pb(all[p]);
						else b.pb(all[p]);
					}
				}
			}
			if(j == sz || ask(a, b)) {
				vector<int> aa, bb;
				for(int x : a) {
					aa.insert(aa.end(), all(g[x]));
				}
				for(int x : b) {
					bb.insert(bb.end(), all(g[x]));
				}
				pair<int, int> ans = find(aa, bb);
				setRoad(ans.ff, ans.ss);
				merge(ans.ff, ans.ss);
				break;
			}
		}

		while(all.size() && all.back() == -1) {
			all.pop_back();
		}
	}
}

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 604 KB Ok! 104 queries used.
2 Correct 4 ms 604 KB Ok! 105 queries used.

Subtask #2
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 604 KB Ok! 571 queries used.
2 Correct 26 ms 600 KB Ok! 638 queries used.
3 Correct 26 ms 636 KB Ok! 644 queries used.

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 72 ms 600 KB Ok! 1396 queries used.
2 Correct 82 ms 600 KB Ok! 1597 queries used.
3 Correct 85 ms 632 KB Ok! 1561 queries used.
4 Correct 79 ms 620 KB Ok! 1573 queries used.

Subtask #4
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 84 ms 632 KB Ok! 1502 queries used.
2 Correct 88 ms 872 KB Ok! 1559 queries used.
3 Correct 79 ms 604 KB Ok! 1573 queries used.
4 Correct 75 ms 620 KB Ok! 1404 queries used.

Subtask #5
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 81 ms 600 KB Ok! 1579 queries used.
2 Correct 80 ms 636 KB Ok! 1579 queries used.
3 Correct 88 ms 860 KB Ok! 1593 queries used.
4 Correct 80 ms 856 KB Ok! 1571 queries used.
5 Correct 74 ms 624 KB Ok! 1440 queries used.
6 Correct 80 ms 620 KB Ok! 1589 queries used.

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 89 ms 636 KB Ok! 1594 queries used.
2 Correct 85 ms 632 KB Ok! 1584 queries used.