oj.uz

Submission #247267

# Submission time Handle Problem Language Result Execution time Memory
247267 2020-07-11T08:32:35 Z oolimry Lokahian Relics (FXCUP4_lokahia) C++17
0 / 100
 7 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;
    }

Subtask #1
0 / 100.0

# Verdict Execution time Memory Grader output
1 Partially correct 5 ms 640 KB Partially correct : C = 498
2 Partially correct 5 ms 512 KB Partially correct : C = 304
3 Partially correct 6 ms 640 KB Partially correct : C = 499
4 Partially correct 6 ms 640 KB Partially correct : C = 499
5 Partially correct 5 ms 512 KB Partially correct : C = 419
6 Partially correct 5 ms 512 KB Partially correct : C = 418
7 Partially correct 5 ms 512 KB Partially correct : C = 418
8 Partially correct 5 ms 640 KB Partially correct : C = 498
9 Correct 5 ms 512 KB Correct : C = 0
10 Partially correct 5 ms 640 KB Partially correct : C = 498
11 Partially correct 6 ms 640 KB Partially correct : C = 498
12 Partially correct 5 ms 512 KB Partially correct : C = 418
13 Partially correct 6 ms 640 KB Partially correct : C = 498
14 Partially correct 7 ms 640 KB Partially correct : C = 499
15 Incorrect 5 ms 640 KB Wrong
16 Partially correct 6 ms 640 KB Partially correct : C = 499
17 Partially correct 5 ms 640 KB Partially correct : C = 499
18 Incorrect 5 ms 640 KB Wrong
19 Partially correct 6 ms 640 KB Partially correct : C = 499
20 Incorrect 5 ms 616 KB Wrong
21 Partially correct 6 ms 512 KB Partially correct : C = 419
22 Partially correct 5 ms 640 KB Partially correct : C = 419
23 Partially correct 5 ms 512 KB Partially correct : C = 419
24 Partially correct 5 ms 640 KB Partially correct : C = 418
25 Partially correct 5 ms 640 KB Partially correct : C = 419
26 Partially correct 5 ms 640 KB Partially correct : C = 499
27 Partially correct 7 ms 640 KB Partially correct : C = 498