QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#370027#3047. Wind of ChangefantisRE 0ms0kbC++143.6kb2024-03-28 21:13:122024-03-28 21:13:49

Judging History

你现在查看的是最新测评结果

  • [2024-03-28 21:13:49]
  • 评测
  • 测评结果:RE
  • 用时:0ms
  • 内存:0kb
  • [2024-03-28 21:13:12]
  • 提交

answer

#include<bits/stdc++.h>//0xnnb
using namespace std;
typedef long long ll;
typedef double db;
int read(){
    int x=0,f=1;
    char ch=getchar();
    while(ch<'0'||ch>'9'){
        if(ch=='-')f=-1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9'){
        x=x*10+ch-'0';
        ch=getchar();
    }
    return x*f;
}
const int N=250005;
int n,ee1,ee2,vex1[N],vex2[N];
int siz1[N],siz2[N],maxsiz1[N],maxsiz2[N];
int tot1,tot2,rt1,rt2;
bool vis1[N],vis2[N];
vector<int>fa2[N];
vector<ll>val2[N];
ll ans[N];
ll minn1[N],minn2[N];
int id1[N],id2[N];
struct Node{
	int u,v,next;
	ll w;
}e1[N],e2[N];
void add1(int u,int v,ll w){
	e1[++ee1].u=u,e1[ee1].v=v,e1[ee1].w=w;
	e1[ee1].next=vex1[u],vex1[u]=ee1;
}
void add2(int u,int v,ll w){
	e2[++ee2].u=u,e2[ee2].v=v,e2[ee2].w=w;
	e2[ee2].next=vex2[u],vex2[u]=ee2;
}
void getrt2(int u,int fa){
	siz2[u]=1;
	maxsiz2[u]=0;
	for(int i=vex2[u];i;i=e2[i].next){
		int v=e2[i].v;
		if(v==fa||vis2[v])continue;
		getrt2(v,u);
		siz2[u]+=siz2[v];
		maxsiz2[u]=max(maxsiz2[u],siz2[v]);
	}
	maxsiz2[u]=max(maxsiz2[u],tot2-siz2[u]);
	if((!rt2)||maxsiz2[u]<maxsiz2[rt2]){
		rt2=u;
	}
}
void getdis2(int u,int fa,int rt,ll sum){
	fa2[u].push_back(rt);
	val2[u].push_back(sum);
	for(int i=vex2[u];i;i=e2[i].next){
		int v=e2[i].v;
		ll w=e2[i].w;
		if(v==fa||vis2[v])continue;
		getdis2(v,u,rt,sum+w);
	}
}
void dfs2(int u){
	vis2[u]=1;
	getdis2(u,0,u,0);
	for(int i=vex2[u];i;i=e2[i].next){
		int v=e2[i].v;
		if(vis2[v])continue;
		tot2=siz2[v],rt2=0;
		getrt2(v,0);
		dfs2(rt2);
	}
}
void getrt1(int u,int fa){
	siz1[u]=1;
	maxsiz1[u]=0;
	for(int i=vex1[u];i;i=e1[i].next){
		int v=e1[i].v;
		if(v==fa||vis1[v])continue;
		getrt1(v,u);
		siz1[u]+=siz1[v];
		maxsiz1[u]=max(maxsiz1[u],siz1[v]);
	}
	maxsiz1[u]=max(maxsiz1[u],tot1-siz1[u]);
	if((!rt1)||maxsiz1[u]<maxsiz1[rt1]){
		rt1=u;
	}
}
void solve1(int u,int fa,ll sum){
	int tmp=fa2[u].size();
	for(int i=0;i<tmp;i++){
		int faa=fa2[u][i];
		ll w=sum+val2[u][i];
		int id=u;
		if(w<minn1[faa]){
			swap(w,minn1[faa]),swap(id,id1[faa]);
		}
		if(w<minn2[faa]){
			swap(w,minn2[faa]),swap(id,id2[faa]);
		}
	}
	for(int i=vex1[u];i;i=e1[i].next){
		int v=e1[i].v;
		if(v==fa||vis1[v])continue;
		ll w=e1[i].w;
		solve1(v,u,sum+w);
	}
}
void solve2(int u,int fa,ll sum){
	int tmp=fa2[u].size();
	for(int i=0;i<tmp;i++){
		int faa=fa2[u][i];
		if(id1[faa]!=u){
			ans[u]=min(ans[u],sum+val2[u][i]+minn1[faa]);
		}
		else{
			ans[u]=min(ans[u],sum+val2[u][i]+minn2[faa]);
		}
	}
	for(int i=vex1[u];i;i=e1[i].next){
		int v=e1[i].v;
		if(v==fa||vis1[v])continue;
		ll w=e1[i].w;
		solve2(v,u,sum+w);
	}
}
void solve3(int u,int fa){
	int tmp=fa2[u].size();
	for(int i=0;i<tmp;i++){
		int faa=fa2[u][i];
		minn1[faa]=minn2[faa]=1e18;
		id1[faa]=id2[faa]=0;
	}
	for(int i=vex1[u];i;i=e1[i].next){
		int v=e1[i].v;
		if(v==fa||vis1[v])continue;
		solve3(v,u);
	}
}
void dfs1(int u){
	vis1[u]=1;
	solve1(u,0,0);
	solve2(u,0,0);
	solve3(u,0);
	for(int i=vex1[u];i;i=e1[i].next){
		int v=e1[i].v;
		if(vis1[v])continue;
		tot1=siz1[v],rt1=0;
		getrt1(v,0);
		dfs1(rt1);
	}
}
int main(){
    n=read();
    for(int i=1;i<n;i++){
    	int u=read(),v=read(),w=read();
    	add1(u,v,w);
    	add1(v,u,w);
	}
	for(int i=1;i<n;i++){
    	int u=read(),v=read(),w=read();
    	add2(u,v,w);
    	add2(v,u,w);
	}
	tot2=n;
	getrt2(1,0);
	dfs2(rt2);
	tot1=n;
	getrt1(1,0);
	for(int i=1;i<=n;i++){
		ans[i]=minn1[i]=minn2[i]=1e18;
	}
	dfs1(rt1);
	for(int i=1;i<=n;i++){
		printf("%lld\n",ans[i]);
	}
    return 0;
}

详细

Test #1:

score: 0
Runtime Error

input:

250000
137466 116241 624409157
188961 163586 148491970
13958 122239 46409636
186120 44010 919858866
72320 102560 92679302
158544 236582 882613876
22331 114267 646741536
210782 42861 679450428
56693 45397 898958944
71188 114724 904191407
15203 225401 210626781
31071 144225 278121829
110354 83972 4557...

output:


result: