oj.uz

Submission #608542

# Submission time Handle Problem Language Result Execution time Memory
608542 2022-07-27T08:16:50 Z Mr_Husanboy ICC (CEOI16_icc) C++14
100 / 100
 146 ms 512 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;


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:70:29: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   70 |   for(int LOG = 0; (1<<LOG) <comp.size(); LOG ++){
      |                    ~~~~~~~~~^~~~~~~~~~~~
icc.cpp:72:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   72 |    for(int i = 0; i < comp.size(); i++){
      |                   ~~^~~~~~~~~~~~~

Subtask #1
7.0 / 7.0

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

Subtask #2
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 468 KB Ok! 526 queries used.
2 Correct 38 ms 508 KB Ok! 653 queries used.
3 Correct 30 ms 500 KB Ok! 636 queries used.

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 123 ms 492 KB Ok! 1379 queries used.
2 Correct 112 ms 500 KB Ok! 1593 queries used.
3 Correct 109 ms 492 KB Ok! 1593 queries used.
4 Correct 120 ms 496 KB Ok! 1481 queries used.

Subtask #4
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 136 ms 496 KB Ok! 1424 queries used.
2 Correct 146 ms 496 KB Ok! 1452 queries used.
3 Correct 104 ms 492 KB Ok! 1575 queries used.
4 Correct 104 ms 496 KB Ok! 1493 queries used.

Subtask #5
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 133 ms 512 KB Ok! 1540 queries used.
2 Correct 111 ms 496 KB Ok! 1515 queries used.
3 Correct 124 ms 492 KB Ok! 1573 queries used.
4 Correct 112 ms 488 KB Ok! 1525 queries used.
5 Correct 106 ms 504 KB Ok! 1442 queries used.
6 Correct 117 ms 496 KB Ok! 1478 queries used.

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 104 ms 488 KB Ok! 1538 queries used.
2 Correct 129 ms 468 KB Ok! 1588 queries used.