oj.uz

Submission #321119

# Submission time Handle Problem Language Result Execution time Memory
321119 2020-11-11T03:41:51 Z seedkin Lokahian Relics (FXCUP4_lokahia) C++17
100 / 100
 2 ms 620 KB 
#include "lokahia.h"
#include <stdio.h>
 
int root[205]; // who is root?
int select[205]; // able to get mana?
 
int findRoot(int r, int leaf) {
	if(r == leaf) return select[r];
 
	int temp = root[leaf];
	select[r] += select[leaf];
	root[leaf] = r;
	select[leaf] = 0;	
 
	return temp == -1 ? select[r]: findRoot(r, temp);
}
 
int getRoot(int n) {
	int r = root[n];
	if(r == -1) return n;
	findRoot(r, n);
	root[n] = getRoot(r);
	return root[n];
}
 
int FindBase(int N){	
    if(N==1) return 0;
	int target = N / 2;	
	int boss[205];
	int bossNum = 0;
	
	for(int i =0; i < N; i++) {
		root[i] = -1;
		select[i] = 1;		
		boss[i] = 0;
	}
 
    int s= 0;
	for(int i =0; i< N; i++) {
        if( s == 0) {
            boss[bossNum++] = i;
            s = 1;
            continue;
        }
		
        if(getRoot(boss[bossNum-1]) == getRoot(i)) {
            s++;
            continue;
        }

        int r = CollectRelics(getRoot(boss[bossNum-1]), getRoot(i));
        if( r == -1) {
            s--;
            if(s == 0) {
                if(i == N-1) return -1;
            }
            continue;
        }
        int num = findRoot(getRoot(r), getRoot(boss[bossNum-1]));
        num = findRoot(getRoot(r),getRoot(i));
        if(num > target) return getRoot(r);
        s++;
	}
 
	int c = boss[bossNum-1];
    
	for(int i =0; i < bossNum-1; i++) {
		int a = boss[i];		
        if(getRoot(c) == getRoot(a)) continue;
		int r = CollectRelics(getRoot(c), getRoot(a));
		if(r == -1) {
			int b = boss[i+1];
			for(int j = a+1; j < b; j++) {
                if(getRoot(c) == getRoot(j)) continue;
				if(getRoot(j) != j) continue;
				r = CollectRelics(getRoot(c), getRoot(j));
				if(r == -1) continue;
				int num = findRoot(getRoot(r), getRoot(c));
				num = findRoot(getRoot(r), getRoot(j));
				if(num > target) return getRoot(r);
			}
			continue;
		}
		int num = findRoot(getRoot(r), getRoot(c));
		num = findRoot(getRoot(r), getRoot(a));
		if(num > target) return getRoot(r);
	}
 
	if(select[getRoot(c)] > target ) return getRoot(c);    
	return -1;
}

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 620 KB Correct : C = 202
2 Correct 1 ms 492 KB Correct : C = 60
3 Correct 1 ms 620 KB Correct : C = 200
4 Correct 1 ms 620 KB Correct : C = 199
5 Correct 1 ms 620 KB Correct : C = 118
6 Correct 1 ms 620 KB Correct : C = 251
7 Correct 1 ms 620 KB Correct : C = 100
8 Correct 1 ms 492 KB Correct : C = 59
9 Correct 1 ms 620 KB Correct : C = 102
10 Correct 1 ms 620 KB Correct : C = 119
11 Correct 1 ms 620 KB Correct : C = 120
12 Correct 1 ms 620 KB Correct : C = 168
13 Correct 1 ms 620 KB Correct : C = 203
14 Correct 1 ms 620 KB Correct : C = 189
15 Correct 1 ms 620 KB Correct : C = 177
16 Correct 1 ms 620 KB Correct : C = 170
17 Correct 1 ms 620 KB Correct : C = 194
18 Correct 0 ms 492 KB Correct : C = 0
19 Correct 1 ms 620 KB Correct : C = 164
20 Correct 1 ms 492 KB Correct : C = 2
21 Correct 1 ms 620 KB Correct : C = 58
22 Correct 1 ms 620 KB Correct : C = 177
23 Correct 1 ms 620 KB Correct : C = 111
24 Correct 1 ms 620 KB Correct : C = 99
25 Correct 1 ms 620 KB Correct : C = 98
26 Correct 1 ms 620 KB Correct : C = 297
27 Correct 2 ms 620 KB Correct : C = 262