Submission #148187

# Submission time Handle Problem Language Result Execution time Memory
148187 2019-08-31T16:52:29 Z 조팍시\n123(#3740, tlwpdus, ainta, cki86201) Lokahian Relics (FXCUP4_lokahia) C++17
0 / 100
7 ms 732 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;
	return v + 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 rev[210], rev2[210];
int FindBase(int N) {
	vector <int> V;
	for(int i=1, p=1, cnt=0, st=i;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;
				p = v;
			}
		}
		if(cnt == 0 || i == N) {
			V.pb(p);
			rev[st] = p;
			rev2[p] = st;
			p = i + 1;
			st = i + 1;
		}
	}
	vector <int> List;
	int res = V.back(), pp = rev2[res];
	for(int i=pp;i<=N;i++) if(arr[i] == 2 || arr[i] == 1) List.pb(i);
	for(int i=1;i<pp;i++) {
		if(arr[i] == 2) {
			int ri = rev[i];
			int v = myc(ri, res);
			if(v != -1) {
				List.pb(i);
				res = v;
				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, res);
					if(v == 1) List.pb(j), res = v;
				}
			}
		}
	}
	if(szz(List) >= N / 2) {
		return res - 1;
	}

	return -1;
}
# Verdict Execution time Memory Grader output
1 Correct 7 ms 640 KB Correct : C = 197
2 Incorrect 6 ms 640 KB Wrong
3 Correct 7 ms 640 KB Correct : C = 197
4 Incorrect 6 ms 640 KB Wrong
5 Incorrect 6 ms 640 KB Wrong
6 Incorrect 7 ms 616 KB Wrong
7 Incorrect 7 ms 640 KB Wrong
8 Correct 6 ms 640 KB Correct : C = 198
9 Incorrect 7 ms 640 KB Wrong
10 Incorrect 6 ms 640 KB Wrong
11 Correct 7 ms 640 KB Correct : C = 118
12 Correct 6 ms 640 KB Correct : C = 203
13 Correct 7 ms 640 KB Correct : C = 298
14 Incorrect 6 ms 640 KB Wrong
15 Correct 6 ms 640 KB Correct : C = 177
16 Correct 6 ms 724 KB Correct : C = 198
17 Incorrect 6 ms 640 KB Wrong
18 Correct 6 ms 732 KB Correct : C = 178
19 Correct 6 ms 640 KB Correct : C = 117
20 Correct 6 ms 512 KB Correct : C = 4
21 Correct 7 ms 640 KB Correct : C = 297
22 Correct 6 ms 512 KB Correct : C = 0
23 Correct 6 ms 720 KB Correct : C = 177
24 Incorrect 6 ms 592 KB Wrong
25 Incorrect 7 ms 640 KB Wrong
26 Incorrect 7 ms 640 KB Wrong
27 Incorrect 7 ms 640 KB Wrong