社区讨论
能否提供几组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 条回复,欢迎继续交流。
正在加载回复...