oj.uz

Submission #918835

# Submission time Handle Problem Language Result Execution time Memory
918835 2024-01-30T13:49:07 Z vjudge1 ICC (CEOI16_icc) C++17
100 / 100
 104 ms 856 KB 
#include <bits/stdc++.h>
using namespace std;
 
typedef long long ll;
 
#include "icc.h"
 
const int N = 200;
 
vector<int> g[N] , par(N , -1) , adj;
 
int union_find(int x) {
	if(par[x] == x) {
		return x;
	}
	par[x] = union_find(par[x]);
	return par[x];
}
 
void union_set(int x, int y) {
	x = union_find(x);
	y = union_find(y);
 
	if(x == y) {
		return;
	}
	if(g[x].size() < g[y].size()) {
		swap(x,y);
	}
	par[y] = x;
	for(auto i : g[y]) {
		g[x].push_back(i);
	}
	g[y].clear();
}
 
mt19937 rng(time(NULL));
 
void run(int n) {
	for(int i=1;i<=n;i++) {
		par[i] = i;
		g[i].push_back(i);
	}
 
	for(int p=0;p<n - 1;p++) {
		set<int> s;
		adj.clear();
		for(int i=1;i<=n;i++) {
			s.insert(union_find(i));
		}
		for(auto i : s) {
			adj.push_back(i);
		}
		shuffle(adj.begin(), adj.end() , rng);
		vector<int>a,b;
		for(int mask = 0;mask < 8;mask++) {
			vector<int> fi, se;
			for(int i=0;i<(int)adj.size();i++) {
				if(i & (1 << mask)) {
					for(auto j : g[adj[i]]) {
						fi.push_back(j);
					}
				}
				else {
					for(int j : g[adj[i]]) {
						se.push_back(j);
					}
				}
			}
 
			if(query(fi.size(), se.size(), fi.data(), se.data())) {
				a = fi;
				b = se;
				break;
			}
		}
		int l = 0, r = a.size();
		int res1 = -1 , res2 = -1;
		sort(a.begin(), a.end());
		sort(b.begin(), b.end());
		reverse(a.begin(), a.end());
		reverse(b.begin(), b.end());
		
		while(l < r) {
			int mid = (l+r)/2;
			vector<int> v;
			for(int i=0;i<=mid;i++) {
				v.push_back(a[i]);
			}
			if(query(v.size(), b.size(), v.data(), b.data())) {
				res1 = v.back();
				r = mid;
			}
			else {
				l = mid+1;
			}
		}
		l = 0, r = b.size();
		while(l < r) {
			int mid = (l+r)/2;
			vector<int> v;
			for(int i=0;i<=mid;i++) {
				v.push_back(b[i]);
			}
			if(query(v.size(), a.size(), v.data(), a.data())) {
				res2 = v.back();
				r = mid;
			} 
			else {
				l = mid+1;
			}
		}
		union_set(res1, res2);
		setRoad(res1, res2);
	}
}

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 600 KB Ok! 107 queries used.
2 Correct 5 ms 600 KB Ok! 111 queries used.

Subtask #2
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 600 KB Ok! 528 queries used.
2 Correct 33 ms 600 KB Ok! 668 queries used.
3 Correct 31 ms 604 KB Ok! 671 queries used.

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 86 ms 600 KB Ok! 1406 queries used.
2 Correct 104 ms 604 KB Ok! 1620 queries used.
3 Correct 101 ms 640 KB Ok! 1573 queries used.
4 Correct 95 ms 632 KB Ok! 1525 queries used.

Subtask #4
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 96 ms 848 KB Ok! 1515 queries used.
2 Correct 93 ms 652 KB Ok! 1507 queries used.
3 Correct 98 ms 600 KB Ok! 1610 queries used.
4 Correct 89 ms 600 KB Ok! 1465 queries used.

Subtask #5
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 97 ms 600 KB Ok! 1599 queries used.
2 Correct 99 ms 600 KB Ok! 1618 queries used.
3 Correct 104 ms 600 KB Ok! 1631 queries used.
4 Correct 99 ms 648 KB Ok! 1613 queries used.
5 Correct 99 ms 600 KB Ok! 1479 queries used.
6 Correct 97 ms 632 KB Ok! 1532 queries used.

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 98 ms 600 KB Ok! 1608 queries used.
2 Correct 101 ms 856 KB Ok! 1621 queries used.