试着写了一个 SPJ,求加入本题。
稍微自测了一下没发现出错。不知道会不会有一些边界漏判把 SPJ 搞崩掉,如果有出错麻烦告知。
此外原英文题面上:
Additionally, if the first line of your output is correct and the other two are missing or incorrect, you will receive about 70% of the value of that test case.
也就是说,如果只输出了答案不输出方案也能得到 70% 的分数,翻译可能是为了 SPJ 实现更方便加入了必须输入 5 个数的条件。我写的这个 SPJ 应该可以实现原题的标准,不知能否把计分标准换成原题的标准?
#include <testlib.h>
#include <algorithm>
#include <cstring>
#include <set>
#include <utility>
const int MaxN = 300000;
int N, Cnt;
int jans = -1, pans = -1;
int U[MaxN + 5], V[MaxN + 5];
std::set< std::pair<int, int> > Edge;
int Par[MaxN + 5];
int find(int x) { return x == Par[x] ? x : Par[x] = find(Par[x]); }
void readInput() {
N = inf.readInt(1, MaxN, "n");
inf.readEoln();
for (int i = 1; i <= N; ++i) Par[i] = i;
for (int i = 1; i < N; ++i) {
int u = inf.readInt(1, N, "a_i");
inf.readSpace();
int v = inf.readInt(1, N, "b_i");
inf.readEoln();
ensuref(u != v, "tree can't contain loops");
ensuref(Edge.count(std::make_pair(u, v)) == 0, "tree can't contain multiple edges between a pair of vertices");
Edge.insert(std::make_pair(u, v));
Edge.insert(std::make_pair(v, u));
U[i] = std::min(u, v), V[i] = std::max(u, v);
int p = find(u), q = find(v);
ensuref(p != q, "tree can't contain cycles");
}
inf.readEof();
}
std::vector<int> Gr[MaxN + 5];
int Dis[MaxN + 5];
void dfs(int u) {
for (int i = 0; i < (int) Gr[u].size(); ++i) {
int v = Gr[u][i];
if (Dis[u] + 1 < Dis[v]) {
Dis[v] = Dis[u] + 1;
dfs(v);
}
}
}
int getDiameter(int cut_u, int cut_v, int link_u, int link_v) {
for (int i = 1; i <= N; ++i) Gr[i].clear();
for (int i = 1; i < N; ++i)
if (U[i] != cut_u || V[i] != cut_v) {
Gr[U[i]].push_back(V[i]);
Gr[V[i]].push_back(U[i]);
}
Gr[link_u].push_back(link_v);
Gr[link_v].push_back(link_u);
memset(Dis, 0x7F, sizeof Dis);
Dis[1] = 0;
dfs(1);
int rt = 1;
for (int i = 1; i <= N; ++i)
if (Dis[i] > Dis[rt]) rt = i;
memset(Dis, 0x7F, sizeof Dis);
Dis[rt] = 0;
dfs(rt);
int dia = 0;
for (int i = 1; i <= N; ++i)
dia = std::max(dia, Dis[i]);
return dia;
}
int readAns(InStream& stream) {
int res = stream.readInt(1, N, "smallest distance between the farthest two rooms");
stream.readEoln();
if (stream.seekEof() == true) return res;
int u = stream.readInt(1, N, "first room of the tunnel to be closed");
stream.readSpace();
int v = stream.readInt(1, N, "second room of the tunnel to be closed");
stream.readEoln();
int a = stream.readInt(1, N, "first room of the tunnel to be opened");
stream.readSpace();
int b = stream.readInt(1, N, "second room of the tunnel to be opened");
stream.readEoln();
stream.readEof();
if (Edge.count(std::make_pair(u, v)) == 0) {
if (jans == -1) quitf(_fail, "the previous tunnel doesn't exist");
else return res;
}
if (u > v) std::swap(u, v);
for (int i = 1; i <= N; ++i) Par[i] = i;
for (int i = 1; i < N; ++i)
if (U[i] != u || V[i] != v) Par[find(U[i])] = find(V[i]);
int p = find(a), q = find(b);
if (p == q) {
if (jans == -1) quitf(_fail, "graph contains cycles after reconstruction");
else return res;
}
if (getDiameter(u, v, a, b) == res) Cnt++;
return res;
}
int main(int argc, char *argv[]) {
registerTestlibCmd(argc, argv);
readInput();
jans = readAns(ans);
pans = readAns(ouf);
if (jans == pans) {
if (Cnt == 2) quitf(_ok, "acceptable solution");
else quitp(0.7, "correct answer, but bad reconstruction");
} else if (jans < pans) {
quitf(_wa, "jury has the better answer: jans = %d, pans = %d\n", jans, pans);
} else {
if (Cnt == 2) quitf(_fail, ":( participant has the better answer: jans = %d, pans = %d\n", jans, pans);
else quitf(_wa, "participant prints a better answer, but the reconstruction can't achieve it");
}
return 0;
}