Submission #608488

#	Time	Username	Problem	Language	Result	Execution time	Memory
608488		Mr_Husanboy	ICC (CEOI16_icc)	C++14	100 / 100	126 ms	536 KiB

icc

#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 (stderr)

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 / 7
• Subtask 2: 11 / 11
• Subtask 3: 22 / 22
• Subtask 4: 21 / 21
• Subtask 5: 29 / 29
• Subtask 6: 10 / 10