QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#895877 | #7610. Bus Lines | 11d10xy | WA | 32ms | 63860kb | C++14 | 4.0kb | 2025-02-12 18:42:33 | 2025-02-12 18:42:35 |
Judging History
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 '