QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#895877#7610. Bus Lines11d10xyWA 32ms63860kbC++144.0kb2025-02-12 18:42:332025-02-12 18:42:35

Judging History

This is the latest submission verdict.

  • [2025-02-12 18:42:35]
  • Judged
  • Verdict: WA
  • Time: 32ms
  • Memory: 63860kb
  • [2025-02-12 18:42:33]
  • Submitted

answer

#include<bits/stdc++.h>
using namespace std;
using i64=long long;
int n,m,fa[200010],mi[21][200010],dep[200010],dfn[200010],raw[200010],out[200010],tot,up[200010];
vector<int>G[200010];
i64 ans[200010];
void dfs0(int u){
   dfn[u]=++tot,raw[tot]=u;
   dep[u]=dep[fa[u]]+1,mi[0][tot]=fa[u];
   for(int v:G[u]){
      G[v].erase(find(begin(G[v]),end(G[v]),u));
      fa[v]=u,dfs0(v);
   }out[u]=tot;
}
inline bool cmp(int x,int y){
   return dfn[x]<dfn[y];
}
void init(){
   for(int i=1;i<=20;i++){
      for(int k=1;k+(1<<i)-1<=n;k++){
         mi[i][k]=min(mi[i-1][k],mi[i-1][k+(1<<i-1)],cmp);
      }
   }
}
inline int lca(int l,int r){
   if(l==r)return l;
   l=dfn[l],r=dfn[r];
   if(l>r)swap(l,r);l++;
   int g=__lg(r-l+1);
   return min(mi[g][l],mi[g][r-(1<<g)+1],cmp);
}
void dfs1(int u){
   for(int v:G[u]){
      dfs1(v),up[u]=min(up[u],up[v],cmp);
   }
}
namespace tr2{
vector<int>T[200010];
int sz[200010];i64 subds[200010];
void dfs(int u){
   sz[u]=1,subds[u]=0;
   for(int v:T[u]){
      dfs(v),sz[u]+=sz[v],subds[u]+=subds[v];
   }subds[u]+=sz[u];
}
void init(){
   for(int i=2;i<=n;i++)T[up[i]].push_back(i);
   dfs(1);
}
}
struct P_{int u,v;};
vector<P_>pr[200010];
namespace ds3{
constexpr int N=200010*50;
i64 sum[200010];
struct T_{
   int u,v;i64 c;
   T_ operator+(const T_&o)const{
      if(!u)return o;
      if(!o.u)return*this;
      return{u,o.v,c+o.c-sum[lca(v,o.u)]};
   }
   i64 eval(int RT){return c-sum[RT];}
}t[N];
int ls[N],rs[N],tot;
inline void pushup(int u){
   t[u]=t[ls[u]]+t[rs[u]];
}
int merge(int x,int y,int l,int r){
   if(!x||!y)return x|y;
   if(l==r)return x;
   int mid=l+r>>1;
   ls[x]=merge(ls[x],ls[y],l,mid);
   rs[x]=merge(rs[x],rs[y],mid+1,r);
   pushup(x);
   return x;
}
void insert(int&u,int l,int r,int x){
   if(!u)u=++tot;
   if(l==r)return t[u]={x,x,sum[x]},void();
   int mid=l+r>>1;
   if(dfn[x]<=mid)insert(ls[u],l,mid,x);
   else insert(rs[u],mid+1,r,x);
   pushup(u);
}
void dfs(int u){
   sum[u]+=tr2::subds[u];
   for(int v:G[u]){
      sum[v]+=sum[u],dfs(v);
   }
}
void init(){dfs(1);}
}
namespace ds4{
i64 w2[200010],w3[200010],s1[200010],s2[200010],so2[200010],ans[200010];
void dfs0(int u){
   for(int v:G[u]){
      so2[v]+=so2[u];
      dfs0(v),w3[u]+=w3[v];
   }
}
void dfs1(int u){
   w2[u]+=so2[u]-so2[up[u]]+n-s1[u];
   for(int v:tr2::T[u]){
      w2[v]+=w2[u];
      dfs1(v);
   }
}
int RT;
vector<int>tmp[200010],vT[200010];
int dfs2(int u){
   int rt=0;
   for(int v:vT[u]){
      int q=dfs2(v);i64 w=ds3::t[q].eval(RT);
      w3[v]+=w,w3[u]-=w,rt=ds3::merge(rt,q,1,n);
   }
   for(int v:tmp[u])ds3::insert(rt,1,n,v);

   return rt;
}
void dfs(int u){
   for(int v:G[u]){
      dfs(v),s1[u]+=s1[v],s2[u]+=s2[v];
   }
   for(int v:G[u]){
      so2[v]=s2[u]-s2[v];
   }ans[u]+=s2[u];
   s1[u]++,s2[u]+=tr2::sz[u];
   vector<int>S;
   for(P_ p:pr[u]){
      S.push_back(p.u),S.push_back(p.v);
      tmp[p.u].push_back(p.v),tmp[p.v].push_back(p.u);
   }
   sort(begin(S),end(S),cmp);
   S.erase(unique(begin(S),end(S)),end(S));
   int n0=S.size();
   for(int i=1;i<n0;i++){
      S.push_back(lca(S[i-1],S[i]));
   }S.push_back(u);
   sort(begin(S),end(S),cmp);
   S.erase(unique(begin(S),end(S)),end(S));
   n0=S.size();
   for(int i=1;i<n0;i++){
      vT[lca(S[i-1],S[i])].push_back(S[i]);
   }
   RT=u;
   dfs2(u);
   for(int x:S){
      tmp[x].clear(),vT[x].clear();
   }
}
void work(){
   dfs(1),dfs0(1),dfs1(1),dfs2(1);
   for(int i=1;i<=n;i++){
      printf("%lld ",w2[i]-w3[i]+ans[i]);
   }
}
}
int main(){
   scanf("%d",&n);
   for(int i=1,u,v;i<n;i++){
      scanf("%d%d",&u,&v);
      G[u].push_back(v),G[v].push_back(u);
   }
   dfs0(1),init();
   for(int i=1;i<=n;i++)up[i]=i;
   scanf("%d",&m);
   for(int i=1,u,v,w;i<=m;i++){
      scanf("%d%d",&u,&v),w=lca(u,v);
      if(u!=w&&v!=w)pr[w].push_back({u,v});
      up[u]=min(up[u],w,cmp);
      up[v]=min(up[v],w,cmp);
   }
   dfs1(1),tr2::init(),ds3::init();
   ds4::work();
   return 0;
}

詳細信息

Test #1:

score: 100
Accepted
time: 2ms
memory: 39440kb

input:

6
1 2
5 4
6 5
3 1
1 5
3
6 1
2 3
6 4

output:

6 9 9 10 7 7 

result:

ok single line: '6 9 9 10 7 7 '

Test #2:

score: 0
Accepted
time: 2ms
memory: 40800kb

input:

2
1 2
1
1 2

output:

1 1 

result:

ok single line: '1 1 '

Test #3:

score: -100
Wrong Answer
time: 32ms
memory: 63860kb

input:

16384
9137 490
3442 7239
1621 6904
13769 10250
14672 12572
14906 9437
6163 12339
15244 12016
3022 8670
3211 9106
11966 14817
15798 15876
6423 7394
894 7695
13877 1983
16342 15158
13574 15932
15125 10722
6989 15683
10335 8801
12301 4246
6166 3893
9347 12073
7897 12195
6510 3101
4526 15385
7017 7001
4...

output:

34355 25479 35436 35610 34284 33678 35452 48890 35501 34283 34417 35637 34250 33925 35594 35622 34262 35714 24908 52229 20394 35377 35763 25482 35368 33831 34534 34160 36000 33432 50848 35728 33594 33857 35911 34746 34440 52412 35550 35831 34102 34175 35425 35987 35794 25988 33938 20517 35356 35786 ...

result:

wrong answer 1st lines differ - expected: '34355 34048 34070 34152 33992 ...5 34333 33814 33294 34266 34337', found: '34355 25479 35436 35610 34284 ... 26015 33843 32938 34621 35928 '