QOJ.ac
QOJ
The 2nd Universal Cup Finals is coming! Check out our event page, schedule, and competition rules!
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#462133 | #2002. Race | Ishar-zdl | Compile Error | / | / | C++14 | 2.0kb | 2024-07-03 14:35:56 | 2024-07-03 14:36:01 |
Judging History
This is the latest submission verdict.
- [2024-07-03 14:36:01]
- Judged
- Verdict: Compile Error
- Time: 0ms
- Memory: 0kb
- [2024-07-03 14:35:56]
- Submitted
answer
#include<bits/stdc++.h>
typedef long long ll;
typedef unsigned long long ull;
inline int read(){char ch=getchar();int x=0,f=1;for(;ch<'0'||ch>'9';ch=getchar())if(ch=='-')f=-1;for(;ch>='0'&&ch<='9';ch=getchar())x=(x<<3)+(x<<1)+(ch^48);return x*f;}
const int N=2e5+10;
int n,k,head[N],d[N],dis[N],top,tot,dep[N],size[N],rt,ans,minn[N];
bool vis[N];
struct EDGE{int v,next,w;}e[N<<1];
inline void add(int u,int v,int w){e[++tot]={v,head[u],w};head[u]=tot;}
inline void findrt(int x,int fa,int cnt){
size[x]=1;int mx=0;
for(int i=head[x],y;i;i=e[i].next){
if(vis[y=e[i].v]||y==fa)continue;
findrt(y,x,cnt);
size[x]+=size[y];
mx=std::max(mx,size[y]);
}
if(mx<=cnt/2)rt=x;
}
inline void calc(int x,int fa){
d[++top]=x;
for(int i=head[x],y;i;i=e[i].next){
if(vis[y=e[i].v]||y==fa)continue;
dep[y]=dep[x]+1;
dis[y]=dis[x]+e[i].w;
calc(y,x);
}
}
inline void solve(int x){
vis[x]=1;minn[0]=0;
std::vector<int> zcnode;
for(int i=head[x],y;i;i=e[i].next){
if(vis[y=e[i].v])continue;
dis[y]=e[i].w;dep[y]=1;
calc(y,x);
for(int j=1;j<=top;++j){
int zc=k-dis[d[j]];
if(zc<0||minn[zc]<0)continue;
if(ans<0)ans=minn[zc]+dep[d[j]];else ans=std::min(ans,minn[zc]+dep[d[j]]);
}
for(int j=1;j<=top;++j){
int val=dis[d[j]];
if(minn[val]<0)minn[val]=dep[d[j]];else minn[val]=std::min(minn[val],dep[d[j]]);
zcnode.push_back(val);
}
top=0;
}
for(int it:zcnode)minn[it]=-1;
for(int i=head[x],y;i;i=e[i].next){
if(vis[y=e[i].v])continue;
findrt(y,x,size[y]);
findrt(rt,0,size[y]);
solve(rt);
}
}
signed main(){
// freopen("in.in","r",stdin);freopen("out.out","w",stdout);
std::ios::sync_with_stdio(false);std::cin.tie(0);std::cout.tie(0);
n=read();k=read();ans=-1;memset(minn,-1,sizeof(minn));
for(int i=1;i<n;++i){
int u=read()+1,v=read()+1,w=read();
// std::cout<<u<<' '<<v<<' '<<w<<'\n';
add(u,v,w),add(v,u,w);
}
findrt(1,0,n),findrt(rt,0,n);
// std::cout<<rt<<'\n';
solve(rt);
std::cout<<ans<<'\n';
}
详细
/usr/bin/ld: /tmp/ccQjKssV.o: in function `main': answer.code:(.text.startup+0x0): multiple definition of `main'; /tmp/cc9v4YKU.o:implementer.cpp:(.text.startup+0x0): first defined here /usr/bin/ld: /tmp/cc9v4YKU.o: in function `main': implementer.cpp:(.text.startup+0x25): undefined reference to `best_path(int, int, int (*) [2], int*)' collect2: error: ld returned 1 exit status