# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
247231 | cheeheng | 로카히아 유적 (FXCUP4_lokahia) | C++17 | 7 ms | 896 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include "lokahia.h"
#include <bits/stdc++.h>
using namespace std;
int Q = 0;
int memo[205][205];
int query(int a, int b){
if(memo[a][b] == 0){
Q ++;
return memo[a][b] = CollectRelics(a, b);
}else{
return memo[a][b];
}
}
int p[205];
int rank1[205];
int setSize[205];
void init(int N){
for(int i = 0; i < N; i ++){
p[i] = i;
rank1[i] = 0;
setSize[i] = 1;
}
}
int findSet(int i){
return (p[i] == i) ? i : (p[i] = findSet(p[i]));
}
bool isSameSet(int i, int j){
return findSet(i) == findSet(j);
}
void unionSet(int i, int j){
if(!isSameSet(i, j)){
int x = findSet(i);
int y = findSet(j);
//printf("setSize: %d %d\n", x, y);
if(rank1[x] > rank1[y]){
p[y] = x;
setSize[x] += setSize[y];
}else{
p[x] = y;
setSize[y] += setSize[x];
if(rank1[x] == rank1[y]){rank1[y] ++;}
}
}
}
int FindBase(int N){
if(N == 1){
return 0;
}
mt19937 rng(58);
uniform_int_distribution<int> rand(0, N-1);
memset(memo, 0, sizeof(memo));
Q = 0;
init(N);
int tries = 0;
while(Q < 600 && tries < 100000){
int R1 = rand(rng);
tries ++;
int R2 = rand(rng);
if(R1 == R2){continue;}
if(isSameSet(R1, R2) && memo[R1][R2] != 0){continue;}
int R3 = query(R1, R2);
if(R3 == -1){continue;}
//printf("Q=%d: %d %d %d\n", Q, R1, R2, R3);
unionSet(R1, R2);
unionSet(R1, R3);
//printf("setSize=%d\n", setSize[findSet(R3)]);
if(setSize[findSet(R3)] > N/2){
return R3;
}
}
return -1;
}
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |