题目描述
IOI 2023 组委会有大麻烦了！他们忘记计划即将到来的 Ópusztaszer 之旅了。然而，或许一切尚未为晚 ......
在 Ópusztaszer 有 \(N\) 个地标，编号为从 \(0\) 到 \(N-1\)。某些地标之间连有双向的道路。任意一对地标之间至多连有一条道路。组委会不知道哪些地标之间有道路相连。
如果对于每三个不同的地标，它们之间都至少连有 \(\delta\) 条道路，我们就称 Ópusztaszer 的路网密度是至少为 \(\delta\) 的。换言之，对所有满足 \(0 \le u \lt v \lt w \lt N\) 的地标三元组 \((u, v, w)\)，配对 \((u,v)\)，\((v,w)\) 和 \((u,w)\) 中至少有 \(\delta\) 个配对中的地标有道路相连。
组委会已知有某个正整数 \(D\)，满足路网密度至少为 \(D\)。注意， \(D\) 的值不会大于 \(3\)。
组委会可以询问 Ópusztaszer 的电话接线员，以获取关于某些地标之间的道路连接信息。在每次询问时，必须给出两个非空的地标数组 \([A[0], \ldots, A[P-1]]\) 和 \([B[0], \ldots, B[R-1]]\)。地标之间必须是两两不同的，即，
- 对于满足 \(0 \le i \lt j \lt P\) 的所有 \(i\) 和 \(j\)，有 \(A[i] \neq A[j]\)；
- 对于满足 \(0 \le i \lt j \lt R\) 的所有 \(i\) 和 \(j\)，有 \(B[i] \neq B[j]\)；
- 对于满足 \(0 \le i \lt P\) 且 \(0\le j \lt R\) 的所有 \(i\) 和 \(j\)，有 \(A[i] \neq B[j]\)。
对每次询问，接线员都会报告是否存在 \(A\) 中的某个地标和 \(B\) 中的某个地标有道路相连。更准确地说，接线员会对满足 \(0 \le i \lt P\) 和 \(0\le j \lt R\) 的所有配对 \(i\) 和 \(j\) 进行尝试。如果其中某对地标 \(A[i]\) 与 \(B[j]\) 之间连有道路，接线员将报告 true。否则，接线员将报告 false。
一条长度为 \(l\) 的路程，被定义为由不同地标 \(t[0], t[1], \ldots, t[l-1]\) 构成的序列，其中对从 \(0\) 到 \(l-2\)（包括 \(0\) 和 \(l-2\)）的所有 \(i\)，地标 \(t[i]\) 和 \(t[i+1]\) 之间都有道路相连。如果不存在长度至少为 \(l+1\) 的路程，则长度为 \(l\) 的某条路程被称为是最长路程。
你的任务是通过询问接线员，帮助组委会在 Ópusztaszer 找一条最长路程。
【数据范围】
- \(3 \le N \le 256\)
- 对于每个测试用例，函数
longest_trip的所有调用中 \(N\) 的累计总和不超过 \(1\,024\)。 - \(1 \le D \le 3\)
询问次数不超过 400。
首先，连通块数量一定不超过 3.
如果连通块数量为2，那么两个连通块一定都是完全图。答案就是两个图中较大的那一个。
不然的话，现在要求一个连通图的最长路。
下面证明这个连通图一定存在哈密顿通路。
考虑现在对前 \(i\) 个数维护了一条哈密顿通路 \(u_1\rightarrow u_2\cdots u_k\)，现在加入 \(i+1\)
- 如果 \(i+1\) 与 \(u\) 有连边，连接 \(i+1\) 和 \(u\).
- 如果 \(i+1\) 与 \(v\) 有连边，连接 \(i+1\) 和 \(v\).
- 否则，\(u,v\) 有连边，原图是一个环。在当中二分出一个点 \(k\) 与 \(i+1\) 有连边，并把环断出来形成一条新的链。
同时我们得到了一个 询问次数 \(O(n\log n)\) 的做法。
一个神奇的优化：维护两条链，设两条链链头分别为 \(x\) 和 \(y\)。链底分别为 \(p\) 和 \(q\)。
考虑加入点 \(i\)
- 如果 \(i\) 与 \(x\) 或 \(y\) 有连边，把 \(i\) 加入那条链
- 否则 \(x,y\) 有连边，把两条链合并成一条，\(i\) 独自一条链。
最后把两条链合并起来。
- 如果\(\{x,p\}\) 和 \(\{y,q\}\)之间有连边，直接接起来。
- 否则两条链都是环，在两条链中分别二分出两个点，满足他们之间有边，并断环合并。
得到了一个 \(2n+2\log n\) 次询问的做法。
考虑优化， 400 大概是 \(1.5n+2\log n\)，所以考虑用三次询问增加两个点。假设两个链链头分别为 \(x,y\)，现在增加两个点 \(a,b\)
- 如果 \(a,b\) 之间有边
- 如果 \(x,y\) 之间有边，就把 \(x,y\) 连接，另一条链设为 \({a,b}\)
- 否则，\(a\) 和 \(x,y\) 之间至少一个有边。用一次操作判断和哪个连接
- 否则如果 \(x\) 和 \(a\) 有边，把 \(a\) 放到 \(x\) 后面。
- 如果 \(a\) 和 \(y\) 有边，合并两条链，把 \(b\) 设为一条链
- 否则 \(b\) 和 \(y\) 一定有边。
- 否则 \(x\) 和 \(b\) 一定有边，\(y\) 的讨论同上。
//#include "longesttrip.h"
#include<bits/stdc++.h>
using namespace std;
vector<int>longest_trip(int N,int D);
bool are_connected(vector<int>A,vector<int>B);
vector<int>mk(vector<int>g)
{
if(g.front()==g.back())
return {g.front()};
return {g.front(),g.back()};
}
std::vector<int> longest_trip(int N, int D)
{
--N;
if(!N)
return {0};
vector<int>g,h;
g.push_back(1),h.push_back(0);
for(int i=2;i<N;i+=2)
{
if(are_connected({i},{i+1}))
{
if(are_connected({g.back()},{h.back()}))
{
while(!h.empty())
g.push_back(h.back()),h.pop_back();
h.push_back(i),h.push_back(i+1);
}
else
{
if(are_connected({g.back()},{i}))
g.push_back(i),g.push_back(i+1);
else
h.push_back(i),h.push_back(i+1);
}
}
else
{
if(are_connected({g.back()},{i}))
{
g.push_back(i);
if(are_connected({h.back()},{i}))
{
while(!h.empty())
g.push_back(h.back()),h.pop_back();
h.push_back(i+1);
}
else
h.push_back(i+1);
}
else
{
g.push_back(i+1);
if(are_connected({h.back()},{i+1}))
{
while(!h.empty())
g.push_back(h.back()),h.pop_back();
h.push_back(i);
}
else
h.push_back(i);
}
}
}
if(N&1^1)
{
if(are_connected({g.back()},{h.back()}))
{
while(!h.empty())
g.push_back(h.back()),h.pop_back();
h.push_back(N);
}
else
{
if(are_connected({g.back()},{N}))
g.push_back(N);
else
h.push_back(N);
}
}
if(are_connected(g,h))
{
if(are_connected(mk(g),mk(h)))
{
vector<int>p;
if(are_connected({g.front()},{h.front()}))
{
p=g;
reverse(p.begin(),p.end());
for(int j:h)
p.push_back(j);
}
else if(are_connected({g.front()},{h.back()}))
{
p=h;
for(int j:g)
p.push_back(j);
}
else if(are_connected({g.back()},{h.back()}))
{
p=g;
for(int i=h.size()-1;~i;--i)
p.push_back(h[i]);
}
else
{
p=g;
for(int j:h)
p.push_back(j);
}
return p;
}
int l=0,r=g.size()-1;
while(l<r)
{
int md=l+r>>1;
vector<int>p;
for(int i=0;i<=md;i++)
p.push_back(g[i]);
if(are_connected(p,h))
r=md;
else
l=md+1;
}
int k=l;
l=0,r=h.size()-1;
while(l<r)
{
int md=l+r>>1;
vector<int>p;
for(int i=0;i<=md;i++)
p.push_back(h[i]);
if(are_connected({g[k]},{p}))
r=md;
else
l=md+1;
}
if(h.front()^h.back())
assert(are_connected({h[l]},{g[k]}));
vector<int>p;
for(int i=l-1;~i;--i)
p.push_back(h[i]);
for(int i=h.size()-1;i>=l;i--)
p.push_back(h[i]);
for(int i=k;~i;--i)
p.push_back(g[i]);
for(int i=g.size()-1;i>k;i--)
p.push_back(g[i]);
return p;
}
else
return g.size()>h.size()? g:h;
}