神奇的错误。。
查看原帖
神奇的错误。。
141335
qwq2519楼主2021/9/4 10:17
#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
#define rep(i,j,k) for(register int i(j);i<=k;++i)

#define drp(i,j,k) for(register int i(j);i>=k;--i)
#define bug puts(~~~~~~~);
#define bugout(x) cout<<x<<endl;
using namespace std;
typedef long long lxl;
template<typename T>
inline T  max(T &a, T &b) {
	return a > b ? a : b;
}
template<typename T>
inline T  min(T &a, T &b) {
	return a < b ? a : b;
}

inline char gt() {
	static char buf[1 << 21], *p1 = buf, *p2 = buf;
	return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1 << 21, stdin), p1 == p2) ? EOF : *p1++;
}
template <typename T>
inline void  read(T &x) {
	register char ch = gt();
	x = 0;
	int w(0);
	while(!(ch >= '0' && ch <= '9'))w |= ch == '-', ch = gt();
	while(ch >= '0' && ch <= '9')x = x * 10 + (ch & 15), ch = gt();
	w ? x = ~(x - 1) : x;
}
template <typename T>
inline void out(T x) {
	if(x < 0) x = -x, putchar('-');
	char ch[20];
	int num(0);
	while(x || !num) ch[++num] = x % 10 + '0', x /= 10;
	while(num) putchar(ch[num--]);
	putchar('\n');
}
const int N = 3e5 + 79;
int n, m, q;
int fa[N], dis[N], dia[N];
bool vis[N];
struct graph {
	int head[N], tot, next[N << 1], ver[N << 1];
	inline void add(int a, int b) {
		ver[++tot] = b;
		next[tot] = head[a];
		head[a] = tot;
	}
} G;

inline int calcdiameter(int x) {
	memset(vis, 0, sizeof vis);
	dis[x] = 0;
	vis[x] = 1;
	queue<int>q;
	q.push(x);
	int st = x;
	while(q.size()) {
		int y = q.front();
		q.pop();
		for(register int i(G.head[y]); i; i = G.next[y]) {
			int v = G.ver[i];
			if(vis[v]) continue;
			vis[v] = 1;
			q.push(v);
			dis[v] = dis[y] + 1;
			if(dis[v] > dis[st]) st = v;
		}
	}

	memset(vis, 0, sizeof vis);
	int ed = st;
	q.push(st);
	dis[st] = 0;
	vis[st] = 1;
	while(q.size()) {
		int y = q.front();
		q.pop();
		for(register int i(G.head[y]); i; i = G.next[i]) {
			int v = G.ver[i];
			if(vis[v]) continue;
			vis[v] = 1;
			q.push(v);
			dis[v] = dis[y] + 1;
			if(dis[v] > dis[ed]) ed = v;
		}
	}
	return dis[ed];
}

inline int find(int x) {
	while(x != fa[x]) x = fa[x] = fa[fa[x]];
	return x;
}

int main() {
	read(n);
	read(m);
	read(q);

	rep(i, 1, n) {
		fa[i] = i;
	}

	int u, v;
	rep(i, 1, m) {
		read(u);
		read(v);
		G.add(u, v);
		G.add(v, u);
		u = find(u);
		v = find(v);
		if(u != v)
			fa[u] = v;
	}
	rep(i, 1, n) {
		if(i == find(i))
			dia[i] = calcdiameter(i);
	}

	int op, x, y;

	while(q--) {
		read(op);
		if(op == 1) {
			read(x);
			x = find(x);
			out(dia[x]);
		} else {
			read(x);
			read(y);

			x = find(x);
			y = find(y);
			if(x == y) continue;
			int& d1 =  dia[x];
			int& d2 =  dia[y];
			fa[x] = y;
			d2 = max(max(d1, d2), (d1 + 1) / 2 + (d2 + 1) / 2 + 1);
		}
	}
	return 0;
}

神奇的错误~~ 2A 1WA 7TLE 讨论区和其他人的提交记录暂时找不到这样的。。memset最多n次,不会吧memset不是很快吗

2021/9/4 10:17
加载中...