Submission #1163311

#	Time	Username	Problem	Language	Result	Execution time	Memory
1163311		Dan4Life	ICC (CEOI16_icc)	C++20	100 / 100	80 ms	584 KiB

icc

#include <bits/stdc++.h>
#include "icc.h"
using namespace std;
#define pb push_back
#define sz(a) (int)a.size()
#define all(a) begin(a),end(a)

using vi = vector<int>;
using ar2 = array<int,2>;

template<int SZ> struct Dsu{
	int p[SZ]; vi v[SZ];
	set<int> comps;
	
	void init(int n){
		comps.clear();
		for(int i = 1; i <= n; i++){
			v[i].clear(); v[i].pb(i);
			p[i]=i, comps.insert(i);
		}
	}
	
	int findSet(int i){ return i==p[i]?i:p[i]=findSet(p[i]); }
	
	bool isSameSet(int i, int j){ return findSet(i)==findSet(j); }
	
	void unionSet(int i, int j){
		int x = findSet(i), y = findSet(j);
		if(x==y) return;
		if(sz(v[x])<sz(v[y])) swap(x,y);
		p[y]=x; for(auto u : v[y]) v[x].pb(u);
		v[y].clear(); v[y].shrink_to_fit(); comps.erase(y);
	}
};

Dsu<101> dsu;

bool query(vi V, vi W){
	int n = sz(V), m = sz(W); int v[n], w[m];
	for(int i = 0; i < n; i++) v[i]=V[i];
	for(int i = 0; i < m; i++) w[i]=W[i];
	return query(n,m,v,w);
}

bool Query(vi V, vi W){
	vi v, w; v.clear(); w.clear();
	for(auto u : V) for(auto x : dsu.v[u]) v.pb(x);
	for(auto u : W) for(auto x : dsu.v[u]) w.pb(x);
	return min(sz(v),sz(w))?query(v,w):0;
}

ar2 solve(vi V, vi W){
	vi v, w; v.clear(); w.clear();
	for(auto u : V) for(auto x : dsu.v[u]) v.pb(x);
	for(auto u : W) for(auto x : dsu.v[u]) w.pb(x);
	
	int x, y, l, r;
	
	l = 0, r = sz(v)-1;
	while(l<r){
		int mid = (l+r)/2; vi vv; vv.clear();
		for(int i = 0; i <= mid; i++) vv.pb(v[i]);
		if(query(vv,w)) r=mid;
		else l=mid+1;
	}
	x = v[l];
	
	l = 0, r = sz(w)-1;
	while(l<r){
		int mid = (l+r)/2; vi ww; ww.clear();
		for(int i = 0; i <= mid; i++) ww.pb(w[i]);
		if(query({x},ww)) r=mid;
		else l=mid+1;
	}
	y = w[l];
	
	return {x,y};
}

void run(int n){
	dsu.init(n); srand(time(0));
	for(int _ = 1; _ < n; _++){
		int num_comps = sz(dsu.comps); 
		bool ok = 0; vi t[2];
		for(int j = 0; j < __lg(num_comps-1); j++){
			t[0].clear(); t[1].clear();
			auto itr = begin(dsu.comps);
			for(int i = 0; i < num_comps; i++)
				t[i>>j&1].pb(*itr), itr++;
			if(Query(t[0],t[1])) { ok=1; break; }
		}
		if(!ok){
			int j = __lg(num_comps-1);
			t[0].clear(); t[1].clear();
			auto itr = begin(dsu.comps);
			for(int i = 0; i < num_comps; i++)
				t[i>>j&1].pb(*itr), itr++;
			ok = 1;
		}
		auto [x,y] = solve(t[0],t[1]);
		setRoad(x,y); dsu.unionSet(x,y);
	}
}

• Subtask 1: 7 / 7
• Subtask 2: 11 / 11
• Subtask 3: 22 / 22
• Subtask 4: 21 / 21
• Subtask 5: 29 / 29
• Subtask 6: 10 / 10