Submission #290651

#	Time	Username	Problem	Language	Result	Execution time	Memory
290651		maximath_1	Park (JOI17_park)	C++11	100 / 100	847 ms	1272 KiB

park

#include "park.h"
#include <vector>
#include <queue>
#include <numeric>
#include <algorithm>
#include <iostream>
using namespace std;

int n;
vector<int> graph, pend;
vector<pair<int, int> > edge;

void ans(pair<int, int> i){
	int u = i.first, v = i.second;
	if(u > v) swap(u, v);
	Answer(u, v);
}

vector<int> subarray(int l, int r, vector<int> a){
	vector<int> rs;
	for(int i = l; i <= r; i ++)
		rs.push_back(a[i]);
	return rs;
}

bool is_con(int nw, vector<int> g){
	vector<int> que(n, 0);
	for(int i : g) que[i] = 1;
	que[nw] = 1;
	return Ask(min(g[0], nw), max(g[0], nw), que.data());
}

bool is_con_via(int nw, vector<int> g, vector<int> p){
	vector<int> que(n, 0);
	for(int i : g) que[i] = 1;
	for(int i : p) que[i] = 1;
	que[nw] = 1;
	return Ask(min(g[0], nw), max(g[0], nw), que.data());
}

void connect(int nd, vector<int> g){
	if(g.empty()) return;
	vector<vector<int> > adj(n);
	vector<bool> active(n, 0);
	for(int i : g) active[i] = 1;
	for(auto e : edge){
		if(active[e.first] && active[e.second]){
			adj[e.first].push_back(e.second);
			adj[e.second].push_back(e.first);
		}
	}

	vector<int> ord;
	vector<bool> vis(n, 0);
	ord.push_back(g[0]); vis[g[0]] = 1;
	queue<int> bfs; bfs.push(g[0]);

	for(; bfs.size(); bfs.pop()){
		int nw = bfs.front();
		for(int nx : adj[nw]) if(!vis[nx]){
			vis[nx] = 1;
			bfs.push(nx);
			ord.push_back(nx);
		}
	}

	if(ord.size() != g.size()){
		vector<int> g1, g2;
		for(int i : g)
			if(vis[i]) g1.push_back(i);
			else g2.push_back(i);
		connect(nd, g1);
		connect(nd, g2);
		return;
	}

	if(!is_con(nd, subarray(0, (int)ord.size() - 1, ord)))
		return;

	int id = (int)ord.size() - 1;
	for(int lf = 0, rg = id, md; lf <= rg;){
		md = (lf + rg) / 2;
		if(is_con(nd, subarray(0, md, ord))){
			id = md;
			rg = md - 1;
		}
		else
			lf = md + 1;
	}

	edge.push_back({nd, ord[id]});
	g.erase(find(g.begin(), g.end(), ord[id]));
	connect(nd, g);
}

vector<int> path;
void find_path(int l, int r){
	vector<int> c;
	if(l == 0) c = graph;
	else c = {l};

	if(is_con(r, c)) path.push_back(r);
	else{
		int id = (int)pend.size() - 1;
		for(int lf = 0, rg = id, md; lf <= rg;){
			md = (lf + rg) / 2;
			if(is_con_via(r, c, subarray(0, md, pend))){
				id = md;
				rg = md - 1;
			}else
				lf = md + 1;
		}
		find_path(l, pend[id]);
		find_path(pend[id], r);
	}
}

void Detect(int T, int N){
	n = N;
	graph.push_back(0);
	pend.resize(N - 1); 
	iota(pend.begin(), pend.end(), 1);

	for(; pend.size();){
		int nw = pend.back();
		path.clear();
		find_path(0, nw);
		for(int u : path){
			connect(u, graph);
			graph.push_back(u);
			pend.erase(find(pend.begin(), pend.end(), u));
		}
	}

	for(pair<int, int> i : edge) ans(i);
	return;
}

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