oj.uz

Submission #25882

# Submission time Handle Problem Language Result Execution time Memory
25882 2017-06-24T17:28:08 Z youaremysky99 Park (JOI17_park) C++14
67 / 100
 316 ms 6216 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;

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]) 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; place[s] = place[t] = 1;
		For(i,0,mid) place[other[i]] = 1;
		
		++asked;
		if (Ask(min(s,t), max(s,t) ,place)) {			
			id = mid;
			r = mid - 1;
		} else l = mid + 1;
	} 

	return other[id];
}	

bool haveEdge(int s, int t) {
	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;
	}
	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;
void dfs(int u) {
	was[u] = true;
	num[u] = ++top;
	for (int v : V[u]) if (!was[v]) dfs(v);
}

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));

	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);
	}
	
	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 0 ms 6084 KB Wrong Answer[6]
2 Halted 0 ms 0 KB -

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 66 ms 6216 KB Output is correct
2 Correct 186 ms 6216 KB Output is correct
3 Correct 163 ms 6216 KB Output is correct
4 Correct 69 ms 6216 KB Output is correct
5 Correct 66 ms 6216 KB Output is correct

Subtask #3
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 206 ms 6216 KB Output is correct
2 Correct 229 ms 6216 KB Output is correct
3 Correct 213 ms 6216 KB Output is correct
4 Correct 223 ms 6216 KB Output is correct
5 Correct 229 ms 6216 KB Output is correct
6 Correct 206 ms 6216 KB Output is correct
7 Correct 219 ms 6216 KB Output is correct
8 Correct 209 ms 6216 KB Output is correct

Subtask #4
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 96 ms 6084 KB Output is correct
2 Correct 216 ms 6216 KB Output is correct
3 Correct 206 ms 6216 KB Output is correct
4 Correct 156 ms 6216 KB Output is correct
5 Correct 186 ms 6216 KB Output is correct
6 Correct 153 ms 6216 KB Output is correct
7 Correct 113 ms 6216 KB Output is correct
8 Correct 189 ms 6216 KB Output is correct
9 Correct 159 ms 6216 KB Output is correct
10 Correct 179 ms 6216 KB Output is correct
11 Correct 216 ms 6216 KB Output is correct
12 Correct 196 ms 6216 KB Output is correct
13 Correct 116 ms 6216 KB Output is correct
14 Correct 203 ms 6216 KB Output is correct
15 Correct 119 ms 6216 KB Output is correct
16 Correct 243 ms 6216 KB Output is correct
17 Correct 63 ms 6216 KB Output is correct
18 Correct 186 ms 6216 KB Output is correct
19 Correct 113 ms 6216 KB Output is correct
20 Correct 183 ms 6216 KB Output is correct

Subtask #5
0 / 23.0

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