15pts/65pts可能的情况
查看原帖
15pts/65pts可能的情况
1379399
reductt楼主2024/7/30 20:59

本人一开始是20pts,代码:

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define FOR(i,a,b) for(int i=a;i<=b;i++)
const int N=3e5+10;
int read(){
	int x=0,f=1;char c=getchar();
	while(c<'0'||'9'<c){if(c=='-')f=-1;c=getchar();}
	while('0'<=c&&c<='9')x=x*10+c-'0',c=getchar();
	return x*f;
}
struct Edge{int u,v,w;}G[2*N];
struct Task{int u,v,len;}task[N];
int n,m,d[N],dis[N],head[N],nxt[2*N],idx;
int top[N],dep[N],siz[N],hson[N],fa[N];
void add_edge(int u,int v,int w){
	G[++idx]={u,v,w},nxt[idx]=head[u],head[u]=idx;
}
void dfs1(int u,int f){
	fa[u]=f,siz[u]=1,dep[u]=dep[f]+1;
	for(int j=head[u];j;j=nxt[j]){
		int v=G[j].v,w=G[j].w;
		if(v==f)continue;
		dis[v]=dis[u]+w;
		dfs1(v,u);
		siz[u]+=siz[v];
		if(siz[v]>siz[hson[u]])hson[u]=v;
	}
}
void dfs2(int u,int t){
	top[u]=t;
	if(!hson[u])return;
	dfs2(hson[u],t);
	for(int j=head[u];j;j=nxt[j]){
		int v=G[j].v;
		if(v!=fa[u]&&v!=hson[u])dfs2(v,v);
	}
}
int lca(int u,int v){
	while(top[u]!=top[v]){
		if(dep[top[u]]>dep[top[v]])u=fa[top[u]];
		else v=fa[top[v]];
	}
	return dep[u]>dep[v]?v:u;
}
int dfs(int u){
	for(int j=head[u];j;j=nxt[j]){
		int v=G[j].v;
		if(v==fa[u])continue;
		d[u]+=dfs(v);
	}
	return d[u];
}
int check(int mid){
	memset(d,0,sizeof(d));
	int cnt=0,maxt=0;
	FOR(i,1,m){
		int u=task[i].u,v=task[i].v,l=task[i].len;
		if(l>mid){
			cnt++;
			maxt=max(maxt,l);
			d[u]++,d[v]++,d[lca(u,v)]-=2;
		}
	}
	dfs(1);
	FOR(i,1,idx){
		int u=G[i].u,v=G[i].v,w=G[i].w;
		if((d[u]==cnt||d[v]==cnt)&&maxt-w<=mid)return 1;
	}
	return 0;
}
signed main(){
	n=read(),m=read();
	FOR(i,1,n-1){
		int u=read(),v=read(),w=read();
		add_edge(u,v,w),add_edge(v,u,w);
	}
	FOR(i,1,m){
		int u=read(),v=read();
		task[i]={u,v,0};
	}
	dfs1(1,0),dfs2(1,1);
	FOR(i,1,m){
		int u=task[i].u,v=task[i].v;
		task[i].len=dis[u]+dis[v]-2*dis[lca(u,v)];
	}
	int l=0,r=1001,ans=0;
	while(l<r){
		int mid=(l+r)>>1;
		if(check(mid))ans=mid,r=mid;
		else l=mid+1;
	}
	printf("%lld",ans);
	return 0;
}

经过找虫,发现锅出在二分上界 rr 只有1001,应该是 1001*N。

然后又交了一发,65pts,代码:

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define FOR(i,a,b) for(int i=a;i<=b;i++)
const int N=3e5+10;
int read(){
	int x=0,f=1;char c=getchar();
	while(c<'0'||'9'<c){if(c=='-')f=-1;c=getchar();}
	while('0'<=c&&c<='9')x=x*10+c-'0',c=getchar();
	return x*f;
}
struct Edge{int u,v,w;}G[2*N];
struct Task{int u,v,len;}task[N];
int cmp(Task t1,Task t2){
	return t1.len>t2.len;
}
int n,m,d[N],dis[N],head[N],nxt[2*N],idx;
int top[N],dep[N],siz[N],hson[N],fa[N];
void add_edge(int u,int v,int w){
	G[++idx]={u,v,w},nxt[idx]=head[u],head[u]=idx;
}
void dfs1(int u,int f){
	fa[u]=f,siz[u]=1,dep[u]=dep[f]+1;
	for(int j=head[u];j;j=nxt[j]){
		int v=G[j].v,w=G[j].w;
		if(v==f)continue;
		dis[v]=dis[u]+w;
		dfs1(v,u);
		siz[u]+=siz[v];
		if(siz[v]>siz[hson[u]])hson[u]=v;
	}
}
void dfs2(int u,int t){
	top[u]=t;
	if(!hson[u])return;
	dfs2(hson[u],t);
	for(int j=head[u];j;j=nxt[j]){
		int v=G[j].v;
		if(v!=fa[u]&&v!=hson[u])dfs2(v,v);
	}
}
int lca(int u,int v){
	while(top[u]!=top[v]){
		if(dep[top[u]]>dep[top[v]])u=fa[top[u]];
		else v=fa[top[v]];
	}
	return dep[u]>dep[v]?v:u;
}
int dfs(int u){
	for(int j=head[u];j;j=nxt[j]){
		int v=G[j].v;
		if(v==fa[u])continue;
		d[u]+=dfs(v);
	}
	return d[u];
}
int check(int mid){
	memset(d,0,sizeof(d));
	int cnt=0,maxt=0;
	FOR(i,1,m){
		int u=task[i].u,v=task[i].v,len=task[i].len;
		if(len<=mid)break;
		cnt++;
		maxt=max(maxt,len);
		d[u]++,d[v]++,d[lca(u,v)]-=2;
	}
	dfs(1);
	FOR(i,1,idx){
		int u=G[i].u,v=G[i].v,w=G[i].w;
		if((d[u]==cnt||d[v]==cnt)&&maxt-w<=mid)return 1;
	}
	return 0;
}
signed main(){
	n=read(),m=read();
	FOR(i,1,n-1){
		int u=read(),v=read(),w=read();
		add_edge(u,v,w),add_edge(v,u,w);
	}
	FOR(i,1,m){
		int u=read(),v=read();
		task[i]={u,v,0};
	}
	dfs1(1,0),dfs2(1,1);
	FOR(i,1,m){
		int u=task[i].u,v=task[i].v;
		task[i].len=dis[u]+dis[v]-2*dis[lca(u,v)];
	}
	sort(task+1,task+m+1,cmp);
	int l=0,r=1001*N,ans=0;
	while(l<r){
		int mid=(l+r)>>1;
		if(check(mid))ans=mid,r=mid;
		else l=mid+1;
	}
	printf("%lld",ans);
	return 0;
}

又经过漫长的找虫,发现是check写挂了,具体来说 :

if((d[u]==cnt||d[v]==cnt)&&maxt-w<=mid)return 1;

这里应该是 uu 和 vv 中深度大的那个点的 d=cntd=cnt 才能判断被经过 cntcnt 次,希望大家不要和我犯一样的错误。

2024/7/30 20:59
加载中...