답안 #247163

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
247163 2020-07-11T06:59:27 Z oolimry 로카히아 유적 (FXCUP4_lokahia) C++17
0 / 100
6 ms 640 KB
    #include "lokahia.h"
    #include <bits/stdc++.h>
    using namespace std;
    typedef pair<int,int> ii;
     
    int p[205];
    int sz[205];
     
    int findSet(int u){
    	if(u == p[u]) return u;
    	else return findSet(p[u]);
    }
     
    int SZ(int u){ return sz[findSet(u)]; }
     
    void unionSet(int u, int P){
    	u = findSet(u), P = findSet(P);
    	p[u] = P;
    	sz[P] += sz[u];
    }
     
    int FindBase(int N){
    	srand(time(NULL));
    	vector<int> v;
    	
    	if(N == 1){
    		return 0;
    	}
    	
    	for(int i = 0;i < N;i++) v.push_back(i);
    	
    	for(int i = 0;i < N;i++){
    		p[i] = i;
    		sz[i] = 1;
    	}
    	
    	int cnt = 0;
    	map<int,int> occur;
    	
    	while(cnt < 300){
    		int a = rand() % N, b = rand() % N;
    		if(a == b) continue;
    		
    		cnt++;
    		int x = CollectRelics(a,b);
    		occur[x]++;
    	}
    	
    	int best = 0;
    	for(int i = 0;i < N;i++){
    		if(occur[best] < occur[i]){
    			best = i;
    		}
    	}
    	
    	int total = 0;
    	for(int i = 0;i < N;i++){
    		if(i == best){
    			total++;
    			continue;
    		}
    		
    		if(CollectRelics(i,best) != -1) total++;
    	}
    	
    	//cout << best;
    	if(total > (N/2)) return best;
    	//assert(false);
    	//cout << best;
    	return -1;
    }
# 결과 실행 시간 메모리 Grader output
1 Partially correct 5 ms 512 KB Partially correct : C = 419
2 Partially correct 5 ms 512 KB Partially correct : C = 419
3 Partially correct 5 ms 640 KB Partially correct : C = 499
4 Partially correct 5 ms 640 KB Partially correct : C = 419
5 Partially correct 6 ms 640 KB Partially correct : C = 499
6 Partially correct 5 ms 512 KB Partially correct : C = 418
7 Partially correct 6 ms 640 KB Partially correct : C = 498
8 Incorrect 5 ms 512 KB Wrong
9 Partially correct 5 ms 640 KB Partially correct : C = 499
10 Partially correct 5 ms 640 KB Partially correct : C = 418
11 Correct 4 ms 512 KB Correct : C = 0
12 Partially correct 6 ms 640 KB Partially correct : C = 499
13 Partially correct 5 ms 640 KB Partially correct : C = 419
14 Partially correct 5 ms 640 KB Partially correct : C = 498
15 Partially correct 5 ms 512 KB Partially correct : C = 418
16 Partially correct 5 ms 640 KB Partially correct : C = 499
17 Partially correct 5 ms 640 KB Partially correct : C = 499
18 Partially correct 6 ms 640 KB Partially correct : C = 498
19 Partially correct 5 ms 640 KB Partially correct : C = 498
20 Partially correct 5 ms 512 KB Partially correct : C = 304
21 Partially correct 5 ms 640 KB Partially correct : C = 418
22 Partially correct 5 ms 640 KB Partially correct : C = 498
23 Partially correct 6 ms 640 KB Partially correct : C = 499
24 Partially correct 5 ms 640 KB Partially correct : C = 498
25 Partially correct 5 ms 640 KB Partially correct : C = 499
26 Partially correct 5 ms 512 KB Partially correct : C = 419
27 Incorrect 5 ms 640 KB Wrong