「JOISC 2017 Day 3」自然公园

发表于
https://loj.ac/problem/2398

题目链接

「JOISC 2017 Day 3」自然公园

做法

考虑链的情况，我们维护一条链 $ l \dots r $ ，每加入一个点 $ x $ ，可以直接判断是 $ x \dots l \dots r $ 或 $ l \dots r \dots x $ ，然后判断 $ x $ 和端点有没有直接的连边，如果有，连上，返回；否则二分出路径上编号最小的点，继续做下去。
对于树的情况，要把整个集合和连进来的点判断。
对于图的情况，每次发现当前点相邻的时候要二分出每条与集合相连的边，由于点的度数不超过 $ 7 $ ，所以能过。 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
#include <bits/stdc++.h>
#include "park.h"
#define rep(i, a, b) for(int i = (a); i <= (b); i++)
#define per(i, a, b) for(int i = (a); i >= (b); i--)
#define pb push_back
using namespace std;
const int MXN = 4010;
int n;

void Answer(int A, int B);
int Ask(int A, int B, int Place[]);

namespace Sub3 {
	int g[MXN], vis[MXN], used[MXN]; vector<int> hv, e[MXN];
	int check(int S, vector<int> G) {
		rep(i, 0, n - 1) g[i] = 0; for(auto v : G) g[v] = 1;
		g[S] = 1; return Ask(min(G[0], S), max(G[0], S), g);
	}
	int Find(int x) {
		int l = 1, r = n - 2, res = n - 1, mid;
		for(; l <= r;) {
			mid = (l + r) >> 1;
			rep(i, 0, mid) g[i] = (vis[i] != 2); rep(i, mid + 1, n - 1) g[i] = (vis[i] == 1);
			g[x] = 1; if(Ask(0, x, g)) res = mid, r = mid - 1; else l = mid + 1;
		}
		return res;
	}
	void dfs(int u, vector<int> &G) { G.pb(u), used[u] = 0; for(auto v : e[u]) if(used[v]) dfs(v, G); }
	void Finde(int x, vector<int> G) {
		if(!check(x, G)) { for(auto v : G) used[v] = 0; return ; }
		int l = 0, r = G.size() - 2, res = G.size() - 1, mid;
		for(; l <= r;) {
			mid = (l + r) >> 1;
			rep(i, 0, n - 1) g[i] = 0; rep(i, 0, mid) g[G[i]] = 1;
			g[x] = 1;
			if(Ask(min(G[0], x), max(G[0], x), g)) res = mid, r = mid - 1; else l = mid + 1;
		}
		int u = G[res]; for(auto i : G) used[i] = 1; used[u] = 0;
		for(auto v : e[u]) if(used[v]) { vector<int> tmp;  dfs(v, tmp), Finde(x, tmp); }
		Answer(min(u, x), max(u, x)), e[u].pb(x), e[x].pb(u);
	}
	void solve(int x) {
		vis[x] = 2; for(; !check(x, hv); solve(Find(x)));
		for(auto v : hv) used[v] = 1;
		vector<int> tmp; dfs(0, tmp), Finde(x, tmp), vis[x] = 1, hv.pb(x);
	}
	void MAIN() { hv.pb(0), vis[0] = 1; rep(i, 1, n - 1) if(!vis[i]) solve(i); }
}
void Detect(int T, int NN) {
	n = NN;
	Sub3::MAIN(); return ;
}