oj.uz

답안 #65374

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
65374 2018-08-07T13:13:37 Z 검수컵(#1978, imsifile) 통행이 제한된 저택 (FXCUP3_key) C++
0 / 100
 3 ms 744 KB 
#include "key.h"
#include <stdio.h>
#include <algorithm>
#include <vector>
using namespace std;

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

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

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++){
		if(v[i]<0) TakeKey2(ld[-v[i]]);
		else 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);
			}
			cns[-par[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
0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 380 KB Output is correct
2 Runtime error 3 ms 744 KB Execution failed because the return code was nonzero
3 Halted 0 ms 0 KB -

Subtask #2
0 / 34.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 380 KB Output is correct
2 Runtime error 3 ms 744 KB Execution failed because the return code was nonzero
3 Halted 0 ms 0 KB -

Subtask #3
0 / 43.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 380 KB Output is correct
2 Runtime error 3 ms 744 KB Execution failed because the return code was nonzero
3 Halted 0 ms 0 KB -