社区讨论

这题有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 条回复,欢迎继续交流。

正在加载回复...