oj.uz

Submission #25884

# Submission time Handle Problem Language Result Execution time Memory
25884 2017-06-24T19:15:21 Z youaremysky99 Park (JOI17_park) C++14
67 / 100
 386 ms 10140 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);
		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);
}

#include <queue>
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;
			queue<int> qu; 
			qu.push(0);
			
			bool rooted[maxn];
			memset(rooted,false,sizeof(rooted));
			while (sz(qu) && deg < 7) {
				int root = qu.front(); qu.pop(); rooted[root] = true;
				if (haveEdge(i,root)) {
					for (int j : V[root]) if (j != i && !rooted[j]) {
						qu.push(j);
					}
				} else {
					memset(used,0,sizeof(used));
					memset(banned,0,sizeof(banned));
					Rep(j,N) if (edge[i][j]) banned[j] = true;
					top = 0;
					memset(was,false,sizeof(was));
					dfs(root);
					int x = findFirst(i,root,used,true);
					if (haveEdge(i,x) && !rooted[x]) {
						qu.push(x);
					}
				}
				deg = 0;
				Rep(j,N) if (edge[i][j]) ++deg;
			}
		}
	}  

	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 Incorrect 3 ms 10008 KB Wrong Answer[6]
2 Halted 0 ms 0 KB -

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 79 ms 10140 KB Output is correct
2 Correct 203 ms 10140 KB Output is correct
3 Correct 179 ms 10140 KB Output is correct
4 Correct 83 ms 10140 KB Output is correct
5 Correct 86 ms 10140 KB Output is correct

Subtask #3
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 239 ms 10140 KB Output is correct
2 Correct 269 ms 10140 KB Output is correct
3 Correct 263 ms 10140 KB Output is correct
4 Correct 253 ms 10140 KB Output is correct
5 Correct 269 ms 10140 KB Output is correct
6 Correct 229 ms 10140 KB Output is correct
7 Correct 246 ms 10140 KB Output is correct
8 Correct 246 ms 10140 KB Output is correct

Subtask #4
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 126 ms 10008 KB Output is correct
2 Correct 233 ms 10140 KB Output is correct
3 Correct 233 ms 10140 KB Output is correct
4 Correct 186 ms 10140 KB Output is correct
5 Correct 216 ms 10140 KB Output is correct
6 Correct 163 ms 10140 KB Output is correct
7 Correct 129 ms 10140 KB Output is correct
8 Correct 223 ms 10140 KB Output is correct
9 Correct 196 ms 10140 KB Output is correct
10 Correct 223 ms 10140 KB Output is correct
11 Correct 213 ms 10140 KB Output is correct
12 Correct 229 ms 10140 KB Output is correct
13 Correct 133 ms 10140 KB Output is correct
14 Correct 219 ms 10140 KB Output is correct
15 Correct 139 ms 10140 KB Output is correct
16 Correct 269 ms 10140 KB Output is correct
17 Correct 83 ms 10140 KB Output is correct
18 Correct 219 ms 10140 KB Output is correct
19 Correct 143 ms 10140 KB Output is correct
20 Correct 203 ms 10140 KB Output is correct

Subtask #5
0 / 23.0

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