oj.uz

Submission #25883

# Submission time Handle Problem Language Result Execution time Memory
25883 2017-06-24T18:05:37 Z youaremysky99 Park (JOI17_park) C++14
67 / 100
 366 ms 10136 KB 
#include "park.h"
#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>
#include <algorithm>

using namespace std;
#define For(i,a,b) for (int i = (a), _b = (b); i <= _b; ++i)
#define Rep(i,a) for (int i = 0, _a = (a); i < _a; i++) 
#define sz(a) ((int)a.size())

const int maxn = 2000;
int place[maxn];
int N;
vector<int> V[maxn];

/// Ask(int a, int b, int place[]), 0-based
/// use Answer(int a, int b) for an edge

vector<int> path;
bool used[maxn];
bool edge[maxn][maxn];
int num[maxn];
int asked = 0;
int banned[maxn];

bool cmp(int i, int j) {
	return num[i] < num[j];
}

int findFirst(int s, int t, bool used[], bool needtoSort = false) {
	if (s == t) return N + 1;
	vector<int> other;
	Rep(i,N) if (!used[i] && !banned[i]) other.push_back(i);
	if (needtoSort) {
		sort(other.begin(), other.end(), cmp);
	}
	if (sz(other) == 0) return N + 1;
	int l = 0, r = sz(other) - 1, id = sz(other) - 1;
	while (l <= r) {
		int mid = (l + r) >> 1;

		memset(place,0,sizeof(place));
		Rep(i,N) if (used[i]) place[i] = 1; 
		For(i,0,mid) place[other[i]] = 1;
		Rep(i,N) if (banned[i]) place[i] = 0;
		place[s] = place[t] = 1;
		++asked;
		if (Ask(min(s,t), max(s,t) ,place)) {			
			id = mid;
			r = mid - 1;
		} else l = mid + 1;
	} 

	return other[id];
}	

bool needAsk[maxn][maxn];
bool haveEdge(int s, int t) {
	if (needAsk[s][t]) return false;
	if (s == t) return false;
	if (edge[s][t]) return 1;
	memset(place,0,sizeof(place));
	place[s] = place[t] = 1;
	++asked;
	if (Ask(min(s,t),max(s,t),place)) {
		edge[s][t] = edge[t][s] = 1;
		V[s].push_back(t); V[t].push_back(s);

		for (int x : V[s]) if (x != t && !edge[x][t]) {
			haveEdge(x,t);
		}
		for (int x : V[t]) if (x != s && !edge[x][s]) {
			haveEdge(x, s);
		}
		return 1;
	}
	needAsk[s][t] = needAsk[t][s] = true;
	return 0;
}

void doFirst(int s, int t) {
	if (haveEdge(s,t)) return;

	memset(used,0,sizeof(used)); used[s] = used[t] = 1;
	int x = findFirst(s,t,used);
	doFirst(s,x);
	doFirst(x,t);
}

bool was[maxn]; 
int top = 0;
int par[maxn];
void dfs(int u) {
	was[u] = true;
	num[u] = ++top;
	for (int v : V[u]) if (!was[v]) dfs(v), par[v] = u;
}

void doSecond(int s, int t, bool was[]) {
	if (!haveEdge(s,t)) {
		memset(used,0,sizeof(used));
		Rep(i,N) if (!was[i]) used[i] = true; used[s] = used[t] = 1;
		int x = findFirst(s,t,used,true);
		doFirst(x,t);
	}

	Rep(i,N) was[i] = false;
	memset(num,0,sizeof(num));
	top = 0;
	dfs(0);
}

void Detect(int T, int _N) {
	N = _N;
	memset(edge,0,sizeof(edge));
	memset(banned,0,sizeof(banned));

	doFirst(0,1);
	memset(was,0,sizeof(was));
	memset(num,0,sizeof(num));
	top = 0;
	dfs(0);
	
	For(i,2,N - 1) if (!was[i]) {
		doSecond(0,i,was);
	}


	if (T == 5 || T == 1) {
		Rep(i,N) {
			if (edge[i][0] || i == 0) {
				int deg = 0;
				Rep(j,N) deg += edge[i][j];
				while (deg < 7) {
					Rep(j,N) if (haveEdge(i,j)) {
						++deg;
					}
				}
			}
		}

		memset(used,0,sizeof(used));
		For(i,1, N - 1) if (!edge[i][0]) {
			int deg = 0;
			Rep(j,N) if (edge[i][j]) ++deg;
			while (deg < 7) {
				memset(banned,0,sizeof(banned));
				banned[4] = true;
				Rep(j,N) if (edge[i][j]) banned[j] = true;
				int x = findFirst(0,i,used,true);
				if (haveEdge(x,i)) {
					++deg;
				} else break;
			}	
		}
	} 

	Rep(u,N) Rep(v,N) if (u < v) if (edge[u][v]) Answer(u,v);
}

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 10004 KB Output is correct
2 Correct 26 ms 10004 KB Output is correct
3 Correct 23 ms 10004 KB Output is correct
4 Incorrect 39 ms 10004 KB Wrong Answer[6]
5 Halted 0 ms 0 KB -

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 83 ms 10136 KB Output is correct
2 Correct 199 ms 10136 KB Output is correct
3 Correct 176 ms 10136 KB Output is correct
4 Correct 86 ms 10136 KB Output is correct
5 Correct 89 ms 10136 KB Output is correct

Subtask #3
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 223 ms 10136 KB Output is correct
2 Correct 249 ms 10136 KB Output is correct
3 Correct 243 ms 10136 KB Output is correct
4 Correct 239 ms 10136 KB Output is correct
5 Correct 239 ms 10136 KB Output is correct
6 Correct 219 ms 10136 KB Output is correct
7 Correct 236 ms 10136 KB Output is correct
8 Correct 246 ms 10136 KB Output is correct

Subtask #4
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 99 ms 10004 KB Output is correct
2 Correct 236 ms 10136 KB Output is correct
3 Correct 219 ms 10136 KB Output is correct
4 Correct 169 ms 10136 KB Output is correct
5 Correct 206 ms 10136 KB Output is correct
6 Correct 176 ms 10136 KB Output is correct
7 Correct 133 ms 10136 KB Output is correct
8 Correct 219 ms 10136 KB Output is correct
9 Correct 186 ms 10136 KB Output is correct
10 Correct 216 ms 10136 KB Output is correct
11 Correct 223 ms 10136 KB Output is correct
12 Correct 226 ms 10136 KB Output is correct
13 Correct 149 ms 10136 KB Output is correct
14 Correct 236 ms 10136 KB Output is correct
15 Correct 123 ms 10136 KB Output is correct
16 Correct 239 ms 10136 KB Output is correct
17 Correct 86 ms 10136 KB Output is correct
18 Correct 219 ms 10136 KB Output is correct
19 Correct 143 ms 10136 KB Output is correct
20 Correct 216 ms 10136 KB Output is correct

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Incorrect 366 ms 10004 KB Wrong Answer[5]
2 Halted 0 ms 0 KB -