oj.uz

답안 #247229

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
247229 2020-07-11T08:15:19 Z cheeheng 로카히아 유적 (FXCUP4_lokahia) C++17
0 / 100
 6 ms 896 KB 
#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)){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;
}

Subtask #1
0 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Partially correct 5 ms 768 KB Partially correct : C = 600
2 Incorrect 6 ms 768 KB Wrong
3 Partially correct 5 ms 768 KB Partially correct : C = 600
4 Correct 6 ms 768 KB Correct : C = 60
5 Partially correct 6 ms 768 KB Partially correct : C = 595
6 Partially correct 5 ms 768 KB Partially correct : C = 405
7 Partially correct 5 ms 768 KB Partially correct : C = 305
8 Partially correct 5 ms 768 KB Partially correct : C = 600
9 Correct 5 ms 896 KB Correct : C = 64
10 Partially correct 5 ms 768 KB Partially correct : C = 600
11 Partially correct 5 ms 768 KB Partially correct : C = 600
12 Correct 5 ms 768 KB Correct : C = 39
13 Partially correct 5 ms 768 KB Partially correct : C = 600
14 Correct 5 ms 768 KB Correct : C = 36
15 Partially correct 6 ms 768 KB Partially correct : C = 600
16 Correct 5 ms 512 KB Correct : C = 0
17 Correct 5 ms 768 KB Correct : C = 182
18 Partially correct 6 ms 768 KB Partially correct : C = 600
19 Partially correct 5 ms 768 KB Partially correct : C = 600
20 Incorrect 6 ms 768 KB Wrong
21 Correct 5 ms 640 KB Correct : C = 2
22 Incorrect 6 ms 768 KB Wrong
23 Partially correct 5 ms 768 KB Partially correct : C = 600
24 Partially correct 5 ms 768 KB Partially correct : C = 313
25 Partially correct 5 ms 768 KB Partially correct : C = 600
26 Partially correct 5 ms 768 KB Partially correct : C = 425
27 Correct 5 ms 768 KB Correct : C = 291