oj.uz

Submission #948831

# Submission time Handle Problem Language Result Execution time Memory
948831 2024-03-18T15:02:39 Z phoenix0423 ICC (CEOI16_icc) C++17
61 / 100
 129 ms 652 KB 
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pll;
#define fastio ios::sync_with_stdio(false), cin.tie(0)
#define pb push_back
#define eb emplace_back
#define f first
#define s second
#define lowbit(x) x&-x
#include "icc.h"
const int maxn = 105;
int n;
int par[maxn];
int root(int x){ return x == par[x] ? x : par[x] = root(par[x]);}
vector<int> comp[maxn];

bool qry(int sa, int sb, vector<int> a, vector<int> b){
	int aa[a.size()], bb[b.size()];
	copy(a.begin(), a.end(), aa), copy(b.begin(), b.end(), bb);
	for(int i = 0; i < a.size(); i++) assert(aa[i] >= 1 && aa[i] <= n);
	for(int i = 0; i < b.size(); i++) assert(bb[i] >= 1 && bb[i] <= n);
	// for(int i = 0; i < a.size(); i++) cout<<aa[i]<<" ";
	// cout<<" | ";
	// for(int i = 0; i < b.size(); i++) cout<<bb[i]<<" ";
	// cout<<"\n";
	// int x;
	// cin>>x;
	// return x;
	return query(sa, sb, aa, bb);
}

// void setRoad(int a, int b){
// 	cout<<"set : "<<a<<" "<<b<<"\n";
// }

void run(int _n){
	n = _n;
	for(int i = 1; i <= n; i++) comp[i].pb(i), par[i] = i;
	random_device rd;
	mt19937 rng(rd());
	for(int rd = 0; rd < n - 1; rd++){
		set<int> st;
		for(int i = 1; i <= n; i++) st.insert(root(i));
		vector<vector<int>> s(2);
		bool c = false;
		while(!c){
			s[0].clear(), s[1].clear();
			for(auto x : st){
				int cur = rng() % 2;
				for(auto u : comp[x]) s[cur].pb(u);
			}
			c = qry(s[0].size(), s[1].size(), s[0], s[1]);
		}
		int l = 0, r = s[0].size() - 1;
		while(l != r){
			int m = (l + r) / 2;
			vector<int> ns;
			for(int i = l; i <= m; i++) ns.pb(s[0][i]);
			c = qry(ns.size(), s[1].size(), ns, s[1]);
			if(c) r = m;
			else l = m + 1;
		}
		vector<int> tmp(1, s[0][l]);
		swap(s[0], tmp);
		l = 0, r = s[1].size() - 1;
		while(l != r){
			int m = (l + r) / 2;
			vector<int> ns;
			for(int i = l; i <= m; i++) ns.pb(s[1][i]);
			c = qry(1, ns.size(), s[0], ns);
			if(c) r = m;
			else l = m + 1;
		}
		setRoad(s[0][0], s[1][l]);
		int a = root(s[0][0]), b = root(s[1][l]);
		par[a] = b;
		for(auto x : comp[a]) comp[b].pb(x);
	}
}

// signed main(void){
// 	int n;
// 	cin>>n;
// 	run(n);
// }

Compilation message

icc.cpp: In function 'bool qry(int, int, std::vector<int>, std::vector<int>)':
icc.cpp:21:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   21 |  for(int i = 0; i < a.size(); i++) assert(aa[i] >= 1 && aa[i] <= n);
      |                 ~~^~~~~~~~~~
icc.cpp:22:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   22 |  for(int i = 0; i < b.size(); i++) assert(bb[i] >= 1 && bb[i] <= n);
      |                 ~~^~~~~~~~~~

Subtask #1
7.0 / 7.0

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

Subtask #2
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 600 KB Ok! 529 queries used.
2 Correct 40 ms 604 KB Ok! 863 queries used.
3 Correct 40 ms 632 KB Ok! 808 queries used.

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 91 ms 648 KB Ok! 1512 queries used.
2 Correct 129 ms 640 KB Ok! 2136 queries used.
3 Correct 106 ms 640 KB Ok! 1753 queries used.
4 Correct 102 ms 636 KB Ok! 1723 queries used.

Subtask #4
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 95 ms 636 KB Ok! 1590 queries used.
2 Correct 97 ms 652 KB Ok! 1624 queries used.
3 Correct 114 ms 636 KB Ok! 1908 queries used.
4 Correct 96 ms 604 KB Ok! 1615 queries used.

Subtask #5
0 / 29.0

# Verdict Execution time Memory Grader output
1 Incorrect 117 ms 632 KB Too many queries! 1917 out of 1775
2 Halted 0 ms 0 KB -

Subtask #6
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 117 ms 600 KB Too many queries! 1931 out of 1625
2 Halted 0 ms 0 KB -