社区讨论
这题有spj吗?
P3549[POI 2013] MUL-Multidrink参与者 3已保存回复 2
讨论操作
快速查看讨论及其快照的属性,并进行相关操作。
- 当前回复
- 2 条
- 当前快照
- 1 份
- 快照标识符
- @mi85yx1v
- 此快照首次捕获于
- 2025/11/21 09:10 4 个月前
- 此快照最后确认于
- 2025/11/21 09:10 4 个月前
并不知道是自己打炸了还是没有。
贡献一个spj,第一次写,不知道有没有写炸:
CPP#include <cstdio>
#include <iostream>
#include <algorithm>
#include "testlib.h"
using namespace std;
const int maxn = 500005;
struct Edge {
int to, dist, nxt;
} e[maxn << 1];
int first[maxn];
inline void add_edge(int from, int to, int dist) {
static int __cnt = 0;
e[++__cnt].nxt = first[from];
first[from] = __cnt;
e[__cnt].to = to;
e[__cnt].dist = dist;
e[++__cnt].nxt = first[to];
first[to] = __cnt;
e[__cnt].to = from;
e[__cnt].dist = dist;
}
int dep[maxn], depp[maxn << 1], ll[maxn];
int n, cnt;
struct Tree {
int no[maxn << 4];
int K;
inline void build_tree() {
for(K = 1; K <= cnt; K <<= 1);
for(int i = 1; i <= cnt; ++i) {
no[i + K] = depp[i];
}
for(int i = K; i; --i) {
no[i] = min(no[i << 1], no[i << 1 | 1]);
}
}
inline int query(int l, int r) {
int ans = 0x3f3f3f3f;
for(l += K - 1, r += K + 1; l ^ r ^ 1; l >>= 1, r >>= 1) {
if(~l & 1) {
ans = min(ans, no[l ^ 1]);
}
if(r & 1) {
ans = min(ans, no[r ^ 1]);
}
}
return ans;
}
} tr;
inline void dfs(int now) {
ll[now] = ++cnt;
depp[cnt] = dep[now];
for(int i = first[now]; i; i = e[i].nxt) {
int to = e[i].to;
if(!dep[to]) {
dep[to] = dep[now] + e[i].dist;
dfs(to);
depp[++cnt] = dep[now];
}
}
}
inline int lca_dep(int a, int b) {
return tr.query(min(ll[a], ll[b]) , max(ll[a], ll[b]));
}
inline int getdist(int aa, int bb) {
return dep[aa] + dep[bb] - (lca_dep(aa, bb) << 1);
}
bool Vis[maxn];
int main(int argc, char** argv) {
registerTestlibCmd(argc, argv);
int n = inf.readInt();
for(int i = 1, f, t; i < n; ++i) {
f = inf.readInt();
t = inf.readInt();
add_edge(f, t, 1);
}
dep[1] = 1;
dfs(1);
tr.build_tree();
memset(Vis, 0, sizeof(Vis));
string s = ans.readString();
if (s == "BRAK") {
string sss = ouf.readString();
if (sss != "BRAK") {
quitf(_wa, "WA, expected \"BRAK\".");
} else {
quitf(_ok, "The answer is correct.");
}
} else {
string sss = ouf.readString();
if (sss != "1") {
quitf(_wa, "WA");
}
}
int now = 1;
Vis[1] = true;
for (int i = 2; i <= n; ++i) {
int ttt = ouf.readInt(1, n);
if (ttt == now || getdist(now, ttt) > 2 || Vis[ttt]) {
quitf(_wa, "WA");
} else {
Vis[now = ttt] = true;
}
}
quitf(_ok, "AC");
return 0;
}
chen_zhekkksc03
回复
共 2 条回复,欢迎继续交流。
正在加载回复...