oj.uz

Submission #608488

# Submission time Handle Problem Language Result Execution time Memory
608488 2022-07-27T07:56:39 Z Mr_Husanboy ICC (CEOI16_icc) C++14
100 / 100
 126 ms 536 KB 
#include<bits/stdc++.h>


#include "icc.h"
 
 
using namespace std;
using ll = long long;


 
mt19937 rng(123);
#define ld long double
#define ull unsigned long long 
#define ios ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL)
#define all(a) a.begin(), a.end()
#define ff first
#define ss second
#define vi vector<int>
#define vll vector<ll>
#define pii pair<int,int>
#define pll pair<ll,ll>
#define pld pair<ld,ld>
#define setp(x) setprecision(x)


const int mod=1e9+7;
int inf=1e9;
const int LOGN = 20;
const int MXX=3e5;
int mx = 10007 ;
int n,k;

struct DSU{
	vector<int> t, sz;
	void init(int n){
		t.resize(n+1); sz.resize(n+1);
		for(int i=0; i<n; i++) t[i] = i, sz[i] = 1;
	}
	
	int get(int a){
		return (t[a] == a ? a : t[a] = get(t[a]));
	}
	
	void unite(int a, int b){
		a = get(a);
		b = get(b);
		if(a == b) return ;
		if(sz[a] < sz[b]) swap(a, b);
		sz[a] += sz[b];
		t[b] = a;
	}
};

vector<vi> g;
vector<int> con, vis;


int nodef(vector<int> A, vector<int> B){
	int l = 0, r = A.size()-1;
	while(l < r){
		int m = (l + r) / 2;
		vector<int> tem;
		for(int i=l; i<=m; i++){
			tem.push_back(A[i]);
		}
		if(query(tem.size(),B.size(), tem.data(), B.data())){
			r = m;
		}else l = m+1;
	}
	return A[r];
}

void dfs(int a, int par = -1){
	con.push_back(a);
	vis[a] = 1;
	for(auto u:g[a]){
		if(u == par) continue;
		dfs(u, a);
	}
}

void run(int n){
	g.resize(n+5);
	vector<vi> comp;
	for(int i=1; i<=n; i++) comp.push_back(vi{i});
	
	for(int I = 0; I < n-1; I ++){
		vis.assign(n+1, 0);
		for(int LOG = 0; (1<<LOG) <comp.size(); LOG ++){
			vector<int> A, B;
			for(int i = 0; i < comp.size(); i++){
				if(i & (1 << LOG)){
					for(auto u : comp[i]) A.push_back(u);
				}else{
					for(auto u : comp[i]) B.push_back(u);
				}
			}
			if(query(A.size(), B.size(), A.data(), B.data()) == 0){
				continue;
			}
		//	cout << "A: "; for(auto u : A) cout << u << ' '; cout << endl << "B: "; for(auto u : B) cout << u << ' '; cout << endl;
			int node1 = nodef(A,B);
			int node2 = nodef(B,A);
			setRoad(node1, node2);
			g[node1].push_back(node2);
			g[node2].push_back(node1);
			break;
		}
		comp.clear();
		for(int i=1; i<=n; i++){
			if(vis[i]) continue;
			dfs(i);
			comp.push_back(con);
			con.clear();
		}
	}
}

Compilation message

icc.cpp: In function 'void run(int)':
icc.cpp:90:29: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   90 |   for(int LOG = 0; (1<<LOG) <comp.size(); LOG ++){
      |                    ~~~~~~~~~^~~~~~~~~~~~
icc.cpp:92:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   92 |    for(int i = 0; i < comp.size(); i++){
      |                   ~~^~~~~~~~~~~~~

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 468 KB Ok! 95 queries used.
2 Correct 7 ms 512 KB Ok! 98 queries used.

Subtask #2
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 500 KB Ok! 526 queries used.
2 Correct 37 ms 508 KB Ok! 653 queries used.
3 Correct 40 ms 496 KB Ok! 636 queries used.

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 93 ms 492 KB Ok! 1379 queries used.
2 Correct 113 ms 508 KB Ok! 1593 queries used.
3 Correct 110 ms 492 KB Ok! 1593 queries used.
4 Correct 102 ms 536 KB Ok! 1481 queries used.

Subtask #4
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 108 ms 500 KB Ok! 1424 queries used.
2 Correct 106 ms 496 KB Ok! 1452 queries used.
3 Correct 114 ms 496 KB Ok! 1575 queries used.
4 Correct 99 ms 500 KB Ok! 1493 queries used.

Subtask #5
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 111 ms 500 KB Ok! 1540 queries used.
2 Correct 106 ms 508 KB Ok! 1515 queries used.
3 Correct 104 ms 432 KB Ok! 1573 queries used.
4 Correct 126 ms 492 KB Ok! 1525 queries used.
5 Correct 103 ms 496 KB Ok! 1442 queries used.
6 Correct 111 ms 468 KB Ok! 1478 queries used.

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 109 ms 512 KB Ok! 1538 queries used.
2 Correct 124 ms 496 KB Ok! 1588 queries used.