oj.uz

답안 #141094

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
141094 2019-08-06T16:31:05 Z babo 통행이 제한된 저택 (FXCUP3_key) C++14
0 / 100
 1000 ms 732 KB 
#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) + j){
				//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++){
			if(cyc[i].size() > j) while(1);
			Report_cycle(cyc[i]);
		}
		//cout << '\n';
	}
}

Compilation message

key.cpp: In function 'void EnsureKeyInfo(int)':
key.cpp:95:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
     mi = lo + hi >> 1;
          ~~~^~~~
key.cpp:111:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    if(cyc[i].size() > j) while(1);
       ~~~~~~~~~~~~~~^~~

Subtask #1
0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 3 ms 632 KB Output is correct
3 Correct 2 ms 732 KB Output is correct
4 Execution timed out 1067 ms 632 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #2
0 / 34.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 3 ms 632 KB Output is correct
3 Correct 2 ms 732 KB Output is correct
4 Execution timed out 1067 ms 632 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #3
0 / 43.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 3 ms 632 KB Output is correct
3 Correct 2 ms 732 KB Output is correct
4 Execution timed out 1067 ms 632 KB Time limit exceeded
5 Halted 0 ms 0 KB -