Submission #141097

#	Time	Username	Problem	Language	Result	Execution time	Memory
141097		babo	Key of Impassable Doors (FXCUP3_key)	C++14	0 / 100	3 ms	1144 KiB

key

#include "key.h"
#include <bits/stdc++.h>
#define va first
#define vb second
using namespace std;
using pii = pair<int,int>;

int par[1005];
vector<int> cyc[1005], P[1005];
int sz[1005];
int n_cyc, clk;
int cycid[1005];
int chk[1005];

int gsz(int i){
	TakeKey(i);
	return Explore();
}

int gsz_range(int s, int e, vector<int>& T, int u){
	for(int i = s; i <= e; i++) TakeKey(T[i]);
	TakeKey(u);
	int K = Explore();
	//cout << "gsz_range = " << K << '\n';
	return K;
}

int get_union(int s, int e, vector<int>& T, int lim){
	++clk;
	int cnt = 0;
	for(int i = s; i <= e && i < lim; i++){
		int t = T[i];
		while(true){
			if(!par[t]){
				if(chk[t] == clk) break;
				for(int u : cyc[ cycid[t] ]){
					chk[u] = clk;
					++cnt;
				}
				break;
			}
			if(chk[t] == clk) break;
			chk[t] = clk; ++cnt;
			t = par[t];
		}
	}
	for(int i = lim; i <= e; i++) cnt += sz[ T[i] ];
	//cout << "get_union = " << cnt << '\n';
	return cnt;
}

void Report_tree(int s, int t){
	while(par[t]){		
		Report(s, t);
		t = par[t];
	}
	for(int u : cyc[cycid[t]]) Report(s, u);
}

void Report_cycle(vector<int>& C){
	for(int u : C){
		for(int v : C){
			if(u != v) Report(u, v);
		}
	}
}

void EnsureKeyInfo(int n) {
	for(int i = 1; i <= n; i++){
		int g = gsz(i);
		P[g].push_back(i);
		sz[i] = g;
		Report(i, i);
	}
	for(int u : P[1]){
		cycid[u] = ++n_cyc;
		cyc[n_cyc].push_back(u);
	}
	for(int j = 2; j <= n; j++){
		int s_cyc = n_cyc + 1;
		//cout << "j = " << j << '\n';
		int capt = P[j-1].size();
		for(int u : P[j]){
			//cout << "u = " << u << '\n';
			int lo = 0, hi = (int)P[j-1].size()-1, mi;
			//cout << "P : "; for(int k : P[j-1]) cout << k << ' '; cout << '\n';
			if(gsz_range(lo, hi, P[j-1], u) > get_union(lo, hi, P[j-1], capt) + 1){
				//cout << "making new cycle\n";
				P[j-1].push_back(u);
				cycid[u] = ++n_cyc;
				cyc[n_cyc].push_back(u);
				continue;
			}
			while(lo < hi){
				mi = lo + hi >> 1;
				if(gsz_range(lo, mi, P[j-1], u) > get_union(lo, mi, P[j-1], capt) + 1) lo = mi + 1;	
				else hi = mi;
			}
			//cout << "bs result : " << P[j-1][lo] << '\n';
			if(lo < capt){
				par[u] = P[j-1][lo];
				Report_tree(u, P[j-1][lo]);
			}
			else{
				cycid[u] = cycid[ P[j-1][lo] ];
				cyc[cycid[ P[j-1][lo] ]].push_back(u);
			}
		}
		
		for(int i = s_cyc; i <= n_cyc; i++){
			assert(cyc[i].size() == j);
			Report_cycle(cyc[i]);
		}
		//cout << '\n';
	}
}

Compilation message (stderr)

key.cpp: In function 'void EnsureKeyInfo(int)':
key.cpp:95:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
     mi = lo + hi >> 1;
          ~~~^~~~
In file included from /usr/include/c++/7/cassert:44:0,
                 from /usr/include/x86_64-linux-gnu/c++/7/bits/stdc++.h:33,
                 from key.cpp:2:
key.cpp:111:25: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    assert(cyc[i].size() == j);
           ~~~~~~~~~~~~~~^~~~

• Subtask 1: 0 / 23
• Subtask 2: 0 / 34
• Subtask 3: 0 / 43