QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#276586 | #7610. Bus Lines | AllTheWayNorth# | WA | 123ms | 81412kb | C++14 | 6.1kb | 2023-12-05 23:20:55 | 2023-12-05 23:20:56 |
Judging History
answer
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
using namespace std;
typedef long long ll;
struct edge
{
int v,nxt;
}e[2000005];
namespace qwq
{
int st[22][1000005],val[1000005],b[1000005],lg[1000005];
void build(int n)
{
lg[1]=0;
for(int i=2;i<=n;i++)
lg[i]=lg[i/2]+1;
// printf("build:n=%d\n",n);
for(int i=1;i<=n;i++)
{
st[0][i]=b[i];
// printf("%d ",b[i]);
}
// printf("\n");
for(int i=1;i<=20;i++)
for(int j=1;j<=n;j++)
if(val[st[i-1][j]]<=val[st[i-1][j+(1<<(i-1))]])
st[i][j]=st[i-1][j];
else st[i][j]=st[i-1][j+(1<<(i-1))];
}
int query(int l,int r)
{
int nw=lg[r-l+1];
if(val[st[nw][l]]<val[st[nw][r-(1<<nw)+1]])
return st[nw][l];
return st[nw][r-(1<<nw)+1];
}
}
int getans(int u,int v);
namespace SGT
{
int tans[10000005];
int sum[10000005][2],ls[10000005],rs[10000005],ct;
void pushup(int x)
{
if(!ls[x]||!rs[x])
{
sum[x][0]=sum[ls[x]+rs[x]][0];
sum[x][1]=sum[ls[x]+rs[x]][1];
tans[x]=tans[ls[x]+rs[x]];
return;
}
sum[x][0]=sum[ls[x]][0];
sum[x][1]=sum[rs[x]][1];
tans[x]=tans[ls[x]]+tans[rs[x]]+getans(sum[ls[x]][1],sum[rs[x]][0]);
}
int merge(int x,int y)
{
if(!x||!y) return x+y;
ls[x]=merge(ls[x],ls[y]);
rs[x]=merge(rs[x],rs[y]);
pushup(x);
return x;
}
int modify(int x,int l,int r,int qx,int v)
{
if(l>qx||r<qx) return x;
if(!x) x=++ct;
if(l==r)
{
sum[x][0]=sum[x][1]=v;
return x;
}
int mid=(l+r)/2;
ls[x]=modify(ls[x],l,mid,qx,v);
rs[x]=modify(rs[x],mid+1,r,qx,v);
pushup(x);
return x;
}
int F(int x)
{
return tans[x]+getans(sum[x][0],sum[x][1]);
}
}
int n,m,h[1000005],t,sz[1000005],rt,vis[1000005],d[1000005],g[1000005],cov[1000005];
int gg[22][1000005],nid[1000005],sum[1000005],dfn[1000005],cnt,udfn[1000005];
ll nans[1000005],sumnans[1000005],qans[1000005],srt[1000005];
void add(int u,int v)
{
e[++t].v=v;
e[t].nxt=h[u];
h[u]=t;
}
void dfs1(int u,int fa,int ssz)
{
sz[u]=1;
int mx=0;
for(int i=h[u];i;i=e[i].nxt)
{
int v=e[i].v;
if(v==fa||vis[v]) continue;
dfs1(v,u,ssz);
sz[u]+=sz[v];
mx=max(mx,sz[v]);
}
mx=max(mx,ssz-sz[u]);
if(mx*2<=ssz) rt=u;
}
int bt,fir[1000005],las[1000005];
int lca(int u,int v)
{
if(fir[u]>fir[v]) swap(u,v);
return qwq::query(fir[u],fir[v]);
}
void dfs2(int u,int fa,int dep)
{
qwq::val[u]=d[u]=dep;
qwq::b[++bt]=u;
fir[u]=bt;
g[u]=u;
cov[u]=sum[u]=srt[u]=0;
dfn[u]=++cnt;
udfn[cnt]=u;
sz[u]=1;
for(int i=h[u];i;i=e[i].nxt)
{
int v=e[i].v;
if(v==fa||vis[v]) continue;
dfs2(v,u,dep+1);
qwq::b[++bt]=u;
sz[u]+=sz[v];
}
}
void dfs3(int u,int fa)
{
for(int i=h[u];i;i=e[i].nxt)
{
int v=e[i].v;
if(v==fa||vis[v]) continue;
dfs3(v,u);
if(d[g[v]]<d[g[u]]) g[u]=g[v];
cov[u]|=cov[v];
}
}
void dfs4(int u,int fa)
{
if(cov[u]) nans[u]=0,nid[u]=u;
else nans[u]=nans[g[u]]+1,nid[u]=nid[g[u]];
sum[nid[u]]++;
for(int i=h[u];i;i=e[i].nxt)
{
int v=e[i].v;
if(v==fa||vis[v]) continue;
dfs4(v,u);
}
// printf("dfs4:u=%d,fa=%d,nans=%lld,nid=%d\n",u,fa,nans[u],nid[u]);
}
void dfs5(int u,int fa)
{
sumnans[u]=nans[u];
for(int i=h[u];i;i=e[i].nxt)
{
int v=e[i].v;
if(v==fa||vis[v]) continue;
sum[v]+=sum[u];
dfs5(v,u);
sumnans[u]+=sumnans[v];
}
}
int getans(int u,int v)
{
return sum[u]+sum[v]-2*sum[lca(u,v)];
}
int tmp[1000005];
void dfs6(int u,int fa)
{
srt[u]=SGT::modify(srt[u],1,n,dfn[rt],rt);
for(int i=h[u];i;i=e[i].nxt)
{
int v=e[i].v;
if(v==fa||vis[v]) continue;
dfs6(v,u);
srt[u]=SGT::merge(srt[u],srt[v]);
}
tmp[u]=SGT::F(srt[u])/2;
//qans[u]-=SGT::F(srt[u]);
}
int col[1000005];
void dfz(int u,vector<pair<int,int> > p)
{
int len=p.size();
for(int i=0;i<len;i++)
if(p[i].first>p[i].second)
swap(p[i].first,p[i].second);
sort(p.begin(),p.end());
len=unique(p.begin(),p.end())-p.begin();
//printf("dfz:u=%d,len=%d----\n",u,len);
p.resize(len);
dfs1(u,0,0);
dfs1(u,0,sz[u]);
int nrt=rt;
bt=cnt=0;
dfs2(nrt,0,1);
qwq::build(bt);
len=p.size();
// printf("dfz:u=%d,nrt=%d----\n",u,nrt);
for(int i=0;i<len;i++)
{
int u=p[i].first,v=p[i].second,l=lca(u,v);
if(d[g[u]]>d[l]) g[u]=l;
if(d[g[v]]>d[l]) g[v]=l;
if(l==nrt) cov[u]=cov[v]=1;
}
dfs3(nrt,0);
dfs4(nrt,0);
dfs5(nrt,0);
// printf("dfz:u=%d----\n",u);
int nw=0;
vector<int> son;
qans[nrt]+=sumnans[nrt]+sz[nrt]-sum[nrt];
for(int i=h[nrt];i;i=e[i].nxt)
{
int v=e[i].v;
if(vis[v]) continue;
son.push_back(v);
for(int j=dfn[v];j<dfn[v]+sz[v];j++)
{
int x=udfn[j];
qans[x]+=(sumnans[nrt]-sumnans[v])-sum[nrt]+1ll*(sz[nrt]-sz[v])*(nans[x]+1);
if(nid[x]!=nrt)
qans[x]+=(sz[nrt]-sz[v]);
col[x]=nw;
// printf("v=%d,x=%d,qans=%lld\n",v,x,qans[x]);
}
nw++;
}
// printf("dfz:u=%d----\n",u);
vector<vector<pair<int,int> > > ps;
ps.resize(nw);
for(int i=0;i<len;i++)
{
int u=p[i].first,v=p[i].second,l=lca(u,v);
// printf("i=%d,u=%d,v=%d,l=%d,dfn=%d,%d\n",i,u,v,l,dfn[u],dfn[v]);
if(l==nrt)
{
srt[u]=SGT::modify(srt[u],1,n,dfn[v],v);
srt[v]=SGT::modify(srt[v],1,n,dfn[u],u);
}
if(l!=nrt)
ps[col[l]].push_back(p[i]);
else
{
if(u!=nrt) ps[col[u]].push_back(make_pair(u,son[col[u]]));
if(v!=nrt) ps[col[v]].push_back(make_pair(v,son[col[v]]));
}
}
dfs6(nrt,0);
for(int i=dfn[nrt]+1;i<dfn[nrt]+sz[nrt];i++)
{
int x=udfn[i];
if(nid[x]!=nrt)
qans[x]-=tmp[nid[x]];
}
// printf("dfz:u=%d----\n",u);
for(int i=dfn[nrt];i<dfn[nrt]+sz[nrt];i++)
{
int x=udfn[i];
// printf("x=%d,qans=%lld\n",x,qans[x]);
}
nw=0;
vis[nrt]=1;
for(int i=h[nrt];i;i=e[i].nxt)
{
int v=e[i].v;
if(vis[v]) continue;
dfz(v,ps[nw]);
nw++;
}
}
int main()
{
scanf("%d",&n);
for(int i=1;i<n;i++)
{
int u,v;
scanf("%d%d",&u,&v);
add(u,v);
add(v,u);
}
vector<pair<int,int> > p;
scanf("%d",&m);
for(int i=1;i<=m;i++)
{
int u,v;
scanf("%d%d",&u,&v);
p.push_back(make_pair(u,v));
}
dfz(1,p);
for(int i=1;i<=n;i++)
printf("%lld ",qans[i]);
printf("\n");
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 30556kb
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: 30620kb
input:
2 1 2 1 1 2
output:
1 1
result:
ok single line: '1 1 '
Test #3:
score: -100
Wrong Answer
time: 123ms
memory: 81412kb
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:
33847 34618 33612 34151 34156 34413 34080 20432 34117 34020 34059 34169 33923 33983 34069 33888 34064 34129 34054 50496 33552 33915 33993 34626 34031 33801 34131 34112 34360 33727 50081 34136 34444 33985 34302 34182 34440 50751 34134 34447 34001 34608 34143 34359 34167 34316 33522 33943 34417 34182 ...
result:
wrong answer 1st lines differ - expected: '34355 34048 34070 34152 33992 ...5 34333 33814 33294 34266 34337', found: '33847 34618 33612 34151 34156 ... 33757 33811 33248 34266 34294 '