QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#370027 | #3047. Wind of Change | fantis | RE | 0ms | 0kb | C++14 | 3.6kb | 2024-03-28 21:13:12 | 2024-03-28 21:13:49 |
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;
}
Details
Tip: Click on the bar to expand more detailed information
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...