oj.uz

Submission #148186

# Submission time Handle Problem Language Result Execution time Memory
148186 2019-08-31T16:49:40 Z 조팍시\n123(#3740, tlwpdus, ainta, cki86201) Lokahian Relics (FXCUP4_lokahia) C++17
0 / 100
 8 ms 688 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;
}
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;
	}

	return -1;
}

Subtask #1
0 / 100.0

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