Submission #520996

#	Time	Username	Problem	Language	Result	Execution time	Memory
520996		koioi.org-koosaga	Park (JOI17_park)	C++17	100 / 100	362 ms	804 KiB

park

#include "park.h"
#include <bits/stdc++.h>
#define sz(v) ((int)(v).size())
#define all(v) (v).begin(), (v).end()
using namespace std;
typedef long long lint;
typedef pair<lint, lint> pi;
const int MAXN = 1500;

static int Place[1400];

vector<int> gph[MAXN];
vector<int> ord;

int vis[MAXN], sz[MAXN];

void dfs(int x){
	vis[x] = 1;
	sz[x] = 1;
	ord.push_back(x);
	for(auto &y : gph[x]){
		if(!vis[y]){
			dfs(y);
			sz[x] += sz[y];
		}
	}
}

void go(int s, int e, int x, int n){
//	cout <<"go " <<  s << " " << e << " " << x << endl;

	set<int> banned;
	while(banned.count(s) == 0){
		// see if there exists edge in first place (called N+8M times)
		{
			for(int i = 0; i < n; i++) Place[i] = 0;
			for(int i = s; i <= e; i++){
				if(banned.count(i)) continue;
				Place[ord[i]] = 1;
			}
			Place[x] = 1;
			if(Ask(min(ord[s], x), max(ord[s], x), Place) == 0) return;
		}
		// find first position where you can have connection (called M times)
		int connPoint = -1;
		{
			int ns = s, ne = e;
			while(ns != ne){
				int m = (ns + ne) / 2;
				for(int i = 0; i < n; i++) Place[i] = 0;
				Place[ord[s]] = Place[x] = 1;
				for(int i = s; i <= m; i++){
					if(banned.count(i)) continue;
					Place[ord[i]] = 1;
				}
				if(Ask(min(ord[s], x), max(ord[s], x), Place) == 1) ne = m;
				else ns = m + 1;
			}
			connPoint = ns;
		}
		// add edge
		int y = ord[connPoint];
		gph[x].push_back(y);
//		cout << "found edge " << x << " " << y << endl;
		// ban 
		for(int i = connPoint; i <= connPoint + sz[y] - 1; i++){
			banned.insert(i);
		}
		int pos = connPoint + 1;
		while(pos <= connPoint + sz[y] - 1){
			go(pos, pos + sz[ord[pos]] - 1, x, n);
			pos += sz[ord[pos]];
		}
	}
}

void Detect(int T, int N) {
	vector<int> v = {};
	for(int i = 1; i < N; i++){
		auto init = [&](){
			memset(Place, 0, sizeof(Place));
			for(int i = 0; i < N; i++) Place[i] = 1;
		};
		int s = 0, e = sz(v);
		while(s != e){
			int m = (s + e) / 2;
			init();
			for(int i = m; i < sz(v); i++) Place[v[i]] = 0;
			if(Ask(0, i, Place) == 1) e = m;
			else s = m + 1;
		}
		v.insert(v.begin() + s, i);
	}
//	for(auto &i : v) cout << i << " ";
//	cout << "ok??" << endl;
	for(int i = 0; i < sz(v); i++){
		ord.clear();
		memset(sz, 0, sizeof(sz));
		memset(vis, 0, sizeof(vis));
		dfs(0);
		go(0, sz(ord) - 1, v[i], N);
		for(auto &j : gph[v[i]]) gph[j].push_back(v[i]);
	}
	for(int i = 0; i < N; i++){
		for(auto &j : gph[i]) if(i < j) Answer(i, j);
		gph[i].clear();
	}
}

• Subtask 1: 10 / 10
• Subtask 2: 10 / 10
• Subtask 3: 27 / 27
• Subtask 4: 30 / 30
• Subtask 5: 23 / 23