社区讨论

能否提供几组hack帮我debug

P3304[SDOI2013] 直径参与者 2已保存回复 3

讨论操作

快速查看讨论及其快照的属性,并进行相关操作。

当前回复
3 条
当前快照
1 份
快照标识符
@mhjs6ktq
此快照首次捕获于
2025/11/04 07:38
4 个月前
此快照最后确认于
2025/11/04 07:38
4 个月前
查看原帖
样例及其他hack都可以过
CPP
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<vector>
#define int long long
#define PII pair<int,int>
using namespace std;
	int n;
	vector<PII> e[200005];
	int dis[200005],zj=0,k11,k22;
	vector<int> vec;
	int last[200005],flag[200005];
	void dfs1(int u,int fa){
		for(int i=0;i<e[u].size();i++){
			int v=e[u][i].first;
			if(v==fa) continue;
			dis[v]=dis[u]+e[u][i].second;
			if(dis[v]>zj) zj=dis[v],k11=v;
			dfs1(v,u);
		}
	}
	void dfs2(int u,int fa){
		for(int i=0;i<e[u].size();i++){
			int v=e[u][i].first;
			if(v==fa) continue;
			dis[v]=dis[u]+e[u][i].second;
			if(dis[v]>zj) zj=dis[v],k22=v,last[v]=u;
			dfs2(v,u);
		}
	}
signed main(){
	scanf("%lld",&n);
	for(int i=1;i<n;i++){
		int u,v,w;
		scanf("%lld%lld%lld",&u,&v,&w);
		e[u].push_back(PII(v,w));
		e[v].push_back(PII(u,w));
	}
	dis[1]=0;
	dfs1(1,0);
	dis[k11]=0;
	zj=0;
	dfs2(k11,0);
	printf("%lld\n",zj);
	for(int i=k22;i!=k11;i=last[i]){
		flag[i]=1;
	}
	flag[k11]=1;
	int L=k22,R=k11;
	bool FLAGG=true;
	for(int i=k22;i!=k11;i=last[i]){
		for(int j=0;j<e[i].size();j++){
			int v=e[i][j].first,w=e[i][j].second;
			if(flag[v]) continue;
			if(zj-dis[i]==w||dis[i]==w){
				if(zj-dis[i]==w) L=i;
				if(dis[i]==w&&FLAGG){
					R=i;
					FLAGG=false;
				}
				break;
			}
		}
	}
	int cnt=0;
	for(int i=L;i!=R;i=last[i]){
		cnt++;
	}
	printf("%lld",cnt);
	return 0;
}

回复

3 条回复,欢迎继续交流。

正在加载回复...