Submission #21134

#	Time	Username	Problem	Language	Result	Execution time	Memory
21134		khsoo01	Park (JOI17_park)	C++11	67 / 100	169 ms	2284 KiB

park

#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 (stderr)

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
• Subtask 2: 10 / 10
• Subtask 3: 27 / 27
• Subtask 4: 30 / 30
• Subtask 5: 0 / 23