Submission #65395

#	Time	Username	Problem	Language	Result	Execution time	Memory
65395		imsifile	Key of Impassable Doors (FXCUP3_key)	C++98	100 / 100	44 ms	4700 KiB

key

#include "key.h"
#include <stdio.h>
#include <algorithm>
#include <vector>
using namespace std;

int NN, ba[1010], self[1010], par[1010], ccn, ld[1010];
// par[i] = -x (i is in cycle x), ld[x] = leader of cycle x
vector<int> lds[1010]; // lds[i] : leaders that ba[x]=i

int chk[1010], sum;
void TakeKey2(int K){
	while(1){
		if(par[K]<0) K=par[K];
		if(K<0){
			K=ld[-K];
			if(!chk[K]) chk[K]=1, sum+=self[K];
			break;
		}
		if(chk[K]) break;
		chk[K]=1, sum++;
		K=par[K];
	}
}

int ExploreKey(vector<int> &v, int s, int e, int pl){
	if(pl){
		TakeKey(pl);
		for(int i=s; i<=e; i++){
			if(v[i]<0) TakeKey(ld[-v[i]]);
			else TakeKey(v[i]);
		}
		return Explore();
	}
	sum=0;
	for(int i=1; i<=NN; i++) chk[i]=0;
	for(int i=s; i<=e; i++) TakeKey2(v[i]);
	return sum;
}

int cmp(const int &x, const int &y){
	return self[x] < self[y];
}

int para(int ix, vector<int> &v){
	int mi=0, mx=v.size(), md;
	v.push_back(0);
	while(1){
		md = (mi+mx)/2;
		if(mi==mx) break;
		if(ExploreKey(v, mi, md, ix) <= ExploreKey(v, mi, md, 0)+1) mx=md;
		else mi=md+1;
	}
	md = v[md];
	v.pop_back();
	return md;
}

void EnsureKeyInfo(int N) {
	NN = N;
	for(int i=1; i<=N; i++){
		TakeKey(i);
		self[i]=Explore();
	}
	for(int i=0; i<N; i++) ba[i]=i+1;
	sort(ba, ba+N, cmp);
	for(int t=0; t<N; t++){
		int i=ba[t];
		par[i]=para(i, lds[self[i]-1]);
		if(par[i]<=0){
			if(par[i]==0){
				par[i]=-(++ccn), ld[ccn]=i;
				if(self[i]>1) lds[self[i]-1].push_back(-ccn);
				lds[self[i]].push_back(i);
			}
		}
		else lds[self[i]].push_back(i);
	}
	for(int i=1; i<=N; i++){
		int t=i;
		for(; par[t]>0; t=par[t]) Report(i, t);
		for(int j=1; j<=N; j++){
			if(par[t] == par[j]) Report(i, j);
		}
	}
}

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