oj.uz

Submission #173885

# Submission time Handle Problem Language Result Execution time Memory
173885 2020-01-05T17:57:11 Z 조팍시\n123(#3740, tlwpdus, ainta, cki86201) Lokahian Relics (FXCUP4_lokahia) C++17
100 / 100
 3 ms 632 KB 
#include <bits/stdc++.h>
#include "lokahia.h"
using namespace std;

#define Fi first
#define Se second
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
#define all(x) (x).begin(), (x).end()
#define pb push_back
#define szz(x) (int)(x).size()
#define rep(i, n) for(int i=0;i<(n);i++)
typedef tuple<int, int, int> t3;

vector <int> E[210];
void add_edge(int x, int y) {
	E[x].pb(y);
}
int arr[210];
int myc(int x, int y) {
	int v = CollectRelics(x - 1, y - 1);
	if(v == -1) return -1;
	add_edge(v + 1, x);
	add_edge(v + 1, y);
	return 1;
}
vector <int> v;
int chk[210];
void dfs1(int x) {
	chk[x] = 1;
	for(int e : E[x]) if(chk[e] == 0) dfs1(e);
	v.pb(x);
}

int FindBase(int N) {
	vector <int> V;
	for(int i=1, p=1, cnt=0;i<=N;i++) {
		if(i == p) ++cnt, arr[i] = 2;
		else {
			int v = myc(p, i);
			if(v == -1) --cnt;
			else {
				++cnt;
				arr[i] = 1;
			}
		}
		if(cnt == 0 || i == N) {
			V.pb(p);
			p = i + 1;
		}
	}
	vector <int> List;
	int can = V.back();
	for(int i=can;i<=N;i++) if(arr[i] == 2 || arr[i] == 1) List.pb(i);
	for(int i=1;i<can;i++) {
		if(arr[i] == 2) {
			int v = myc(i, can);
			if(v == 1) {
				List.pb(i);
				for(int j=i+1;arr[j]!=2;j++) if(arr[j]) List.pb(j);
			}
			else {
				for(int j=i+1;arr[j]!=2;j++) {
					if(arr[j]) continue;
					int v = myc(j, can);
					if(v == 1) List.pb(j);
				}
			}
		}
	}
	if(szz(List) >= N / 2 + 1) {
		for(int e : List) if(chk[e] == 0) dfs1(e);
		return v.back() - 1;
	}

	return -1;
}

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 632 KB Correct : C = 298
2 Correct 3 ms 632 KB Correct : C = 205
3 Correct 2 ms 632 KB Correct : C = 207
4 Correct 2 ms 632 KB Correct : C = 121
5 Correct 2 ms 504 KB Correct : C = 118
6 Correct 2 ms 452 KB Correct : C = 4
7 Correct 2 ms 632 KB Correct : C = 297
8 Correct 2 ms 504 KB Correct : C = 121
9 Correct 3 ms 632 KB Correct : C = 198
10 Correct 2 ms 504 KB Correct : C = 177
11 Correct 2 ms 632 KB Correct : C = 199
12 Correct 3 ms 632 KB Correct : C = 277
13 Correct 2 ms 552 KB Correct : C = 177
14 Correct 2 ms 632 KB Correct : C = 126
15 Correct 3 ms 632 KB Correct : C = 199
16 Correct 3 ms 632 KB Correct : C = 204
17 Correct 2 ms 632 KB Correct : C = 178
18 Correct 2 ms 504 KB Correct : C = 119
19 Correct 3 ms 632 KB Correct : C = 269
20 Correct 2 ms 632 KB Correct : C = 198
21 Correct 2 ms 376 KB Correct : C = 0
22 Correct 2 ms 504 KB Correct : C = 119
23 Correct 3 ms 632 KB Correct : C = 204
24 Correct 2 ms 508 KB Correct : C = 167
25 Correct 3 ms 632 KB Correct : C = 279
26 Correct 3 ms 632 KB Correct : C = 201
27 Correct 3 ms 632 KB Correct : C = 255