oj.uz

Submission #21134

# Submission time Handle Problem Language Result Execution time Memory
21134 2017-04-05T02:48:01 Z khsoo01 Park (JOI17_park) C++11
67 / 100
 169 ms 2284 KB 
#include "park.h"
#include<bits/stdc++.h>
using namespace std;
int n;
vector<int> adj[1400], cnd, nw;

bool vis[1400];
static int Place[1400];

void dfs (int cur, int prv) {
	if(cur) cnd.push_back(cur);
	for(auto &nxt : adj[cur]) {
		if(nxt == prv) continue;
		dfs(nxt, cur);
	}
}

int getv (int A, int B) {
	int S = 0, E = cnd.size();
	while(S<E) {
		int mid = (S+E)/2;
		for(int i=0;i<mid;i++) Place[cnd[i]] = 1;
		for(int i=mid;i<cnd.size();i++) Place[cnd[i]] = 0;
		if(Ask(min(A, B), max(A, B), Place)) E = mid;
		else S = mid+1;
	}
	return S;
}

void solve (int S, int E) {
	cnd.clear();
	for(int i=0;i<n;i++) {
		if(i == S || i == E) {
			Place[i] = 1;
		}
		else cnd.push_back(i);
	}
	int tmp = getv(S, E);
	if(!tmp) nw.push_back(S);
	else {
		int mid = cnd[tmp-1];
		solve(S, mid);
		solve(mid, E);
	}
}

void Detect(int T, int N) {
	n = N;
	for(int i=0;i<n;i++) {
		Place[i] = 0;
		vis[i] = false;
		adj[i].clear();
	}
	vis[0] = true;
	for(int i=1;i<n;i++) {
		if(vis[i]) continue;
		vis[i] = true;
		for(int j=0;j<n;j++) {
			Place[j] = 1;
		}
		cnd.clear();
		dfs(0, -1);
		int tmp = getv(0, i);
		nw.clear();
		solve((tmp ? cnd[tmp-1] : 0), i);
		for(int i=0;i+1<nw.size();i++) {
			adj[nw[i]].push_back(nw[i+1]);
			adj[nw[i+1]].push_back(nw[i]);
			Answer(min(nw[i], nw[i+1]), max(nw[i], nw[i+1]));
			vis[nw[i]] = true;
		}
		adj[nw.back()].push_back(i);
		adj[i].push_back(nw.back());
		vis[nw.back()] = true;
		Answer(min(nw.back(), i), max(nw.back(), i));
	}
}

Compilation message

park.cpp: In function 'int getv(int, int)':
park.cpp:23:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i=mid;i<cnd.size();i++) Place[cnd[i]] = 0;
                  ^
park.cpp: In function 'void Detect(int, int)':
park.cpp:66:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i=0;i+1<nw.size();i++) {
                  ^

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 2152 KB Wrong Answer[3]
2 Halted 0 ms 0 KB -

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 73 ms 2284 KB Output is correct
2 Correct 129 ms 2284 KB Output is correct
3 Correct 123 ms 2284 KB Output is correct
4 Correct 73 ms 2284 KB Output is correct
5 Correct 73 ms 2284 KB Output is correct

Subtask #3
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 143 ms 2284 KB Output is correct
2 Correct 169 ms 2284 KB Output is correct
3 Correct 156 ms 2284 KB Output is correct
4 Correct 136 ms 2284 KB Output is correct
5 Correct 146 ms 2284 KB Output is correct
6 Correct 126 ms 2284 KB Output is correct
7 Correct 139 ms 2284 KB Output is correct
8 Correct 139 ms 2284 KB Output is correct

Subtask #4
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 59 ms 2152 KB Output is correct
2 Correct 129 ms 2284 KB Output is correct
3 Correct 146 ms 2284 KB Output is correct
4 Correct 129 ms 2284 KB Output is correct
5 Correct 129 ms 2284 KB Output is correct
6 Correct 106 ms 2284 KB Output is correct
7 Correct 86 ms 2284 KB Output is correct
8 Correct 129 ms 2284 KB Output is correct
9 Correct 113 ms 2284 KB Output is correct
10 Correct 143 ms 2284 KB Output is correct
11 Correct 149 ms 2284 KB Output is correct
12 Correct 133 ms 2284 KB Output is correct
13 Correct 99 ms 2284 KB Output is correct
14 Correct 153 ms 2284 KB Output is correct
15 Correct 99 ms 2284 KB Output is correct
16 Correct 143 ms 2284 KB Output is correct
17 Correct 76 ms 2284 KB Output is correct
18 Correct 136 ms 2284 KB Output is correct
19 Correct 96 ms 2284 KB Output is correct
20 Correct 126 ms 2284 KB Output is correct

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Incorrect 6 ms 2152 KB Wrong Answer[3]
2 Halted 0 ms 0 KB -