QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#227640 | #7610. Bus Lines | 275307894a | TL | 894ms | 38272kb | C++14 | 3.9kb | 2023-10-27 20:25:49 | 2023-10-27 20:25:51 |
Judging History
answer
#include<bits/stdc++.h>
#define Gc() getchar()
#define Me(x,y) memset(x,y,sizeof(x))
#define Mc(x,y) memcpy(x,y,sizeof(x))
#define d(x,y) ((m)*(x-1)+(y))
#define R(n) (rnd()%(n)+1)
#define Pc(x) putchar(x)
#define LB lower_bound
#define UB upper_bound
#define fi first
#define se second
#define eb emplace_back
using namespace std;using ll=long long;using db=double;using lb=long db;using ui=unsigned;using ull=unsigned long long;using pii=pair<int,int>;using LL=__int128;
const int N=2e5+5,M=N*8+5,K=(1<<25)+5,mod=1e9+7,Mod=mod-1;const db eps=1e-9;const int INF=1e9+7;mt19937 rnd(time(0));
int n,x,y;
vector<int> S[N];
int fa[N],d[N],Sn[N],Si[N],Tp[N],Bg[N],Bh,En[N],Df[N];
void dfs1(int x,int La){
fa[x]=La;d[x]=d[La]+1;Si[x]=1;
for(int i:S[x]) if(i^La) dfs1(i,x),Si[x]+=Si[i],Si[Sn[x]]<Si[i]&&(Sn[x]=i);
}
void dfs2(int x,int La){
Df[Bg[x]=++Bh]=x;Tp[x]=La;if(Sn[x]) dfs2(Sn[x],La);
for(int i:S[x]) if(i^fa[x]&&i^Sn[x]) dfs2(i,i);En[x]=Bh;
}
vector<pair<int,int> > E;
int LCA(int x,int y){
E.clear();while(Tp[x]^Tp[y]) {
if(d[Tp[x]]<d[Tp[y]]) swap(x,y);
E.emplace_back(Bg[Tp[x]],Bg[x]);x=fa[Tp[x]];
}
if(d[x]>d[y]) swap(x,y);E.emplace_back(Bg[x],Bg[y]);return x;
}
ll f[N],g[N],w[N],ans[N];int up[N];
vector<pair<int,int> > D[N],Q[N];
namespace Tree{
#define ls v<<1
#define rs v<<1|1
int g[M],Ct;ll Sum[M],f[M];
void Up(int v){f[v]=(g[v]?Sum[v]:f[ls]+f[rs]);}
void PF(int v,int w){g[v]+=w;Up(v);}
void Add(int x,int y,int w,int l=1,int r=n,int v=1){
if(x<=l&&r<=y) return PF(v,w);int m=l+r>>1;
x<=m&&(Add(x,y,w,l,m,ls),0);y>m&&(Add(x,y,w,m+1,r,rs),0);Up(v);
}
void modify(int x,ll w,int l=1,int r=n,int v=1){
Sum[v]+=w;if(l==r) return;int m=l+r>>1;
x<=m?modify(x,w,l,m,ls):modify(x,w,m+1,r,rs);Up(v);
}
ll qry(int x,int y,int op=0,int l=1,int r=n,int v=1){
if(x>y) return 0;op|=g[v];
if(x<=l&&r<=y) return op?Sum[v]:f[v];int m=l+r>>1;
return (x<=m?qry(x,y,op,l,m,ls):0)+(y>m?qry(x,y,op|g[v],m+1,r,rs):0);
}
}
int MIN(int x,int y){return d[x]<d[y]?x:y;}
void ins(int x,int La,int w){
for(auto i:Q[x]) Tree::Add(i.fi,i.se,w);
for(auto i:D[x]) Tree::Add(i.fi,i.se,-2*w);
for(int i:S[x]) if(i^La) ins(i,x,w);
}
void dfs3(int x,int La){
for(int i:S[x]) if(i^La&&i^Sn[x]) dfs3(i,x),ins(i,x,-1);
if(Sn[x]) dfs3(Sn[x],x),ins(Sn[x],x,-1);
// for(int i:S[x]) if(i^La&&i^Sn[x]) ins(i,x,1);
// for(auto i:Q[x]) Tree::Add(i.fi,i.se,1);
// for(auto i:D[x]) Tree::Add(i.fi,i.se,-2);
ins(x,La,1);
f[x]=En[x]-Bg[x]+1;
f[x]+=Tree::qry(Bg[x]+1,En[x]);
for(int i:S[x]) if(i^La) f[x]+=f[i];
w[x]=-f[x];for(int i:S[x]) if(i^La) w[x]+=f[i];
Tree::modify(Bg[x],w[x]);
for(int i:S[x]) if(i^La) up[x]=MIN(up[x],up[i]);
}
void dfs4(int x,int La){
for(int i:S[x]) if(i^La&&i^Sn[x]) dfs4(i,x),ins(i,x,-1);
if(Sn[x]) dfs4(Sn[x],x);
for(int i:S[x]) if(i^La&&i^Sn[x]) ins(i,x,1);
for(auto i:Q[x]) Tree::Add(i.fi,i.se,1);
for(auto i:D[x]) Tree::Add(i.fi,i.se,-2);
g[x]=n-(En[x]-Bg[x]+1);
g[x]+=Tree::f[1]-Tree::qry(Bg[x],En[x]);
// g[x]+=g[up[x]]+f[up[x]];
g[x]-=f[x];
// cerr<<x<<' '<<g[x]<<'\n';
}
void Make(int x,int La){g[x]+=g[up[x]]+f[up[x]];/*cerr<<g[x]<<'\n';*/if(!La) g[x]=0;for(int i:S[x]) if(i^La) Make(i,x);}
void Solve(){
int i,j;scanf("%d",&n);
for(i=1;i<n;i++) {
int x,y;scanf("%d%d",&x,&y);
S[x].eb(y);S[y].eb(x);
}
int Rt=1;
dfs1(Rt,0);dfs2(Rt,Rt);
int m;scanf("%d",&m);
iota(up+1,up+n+1,1);
while(m--){
int x,y;scanf("%d%d",&x,&y);
int Ls=LCA(x,y);up[x]=MIN(up[x],Ls);up[y]=MIN(up[y],Ls);
// for(auto i:E) for(int j=i.fi;j<=i.se;j++) A[x][j]++,A[y][j]++,A[Ls][j]-=2;
for(auto i:E) Q[x].eb(i),Q[y].eb(i),D[Ls].eb(i);
}
dfs3(Rt,0);ins(Rt,0,-1);dfs4(Rt,0);Make(Rt,0);
for(i=1;i<=n;i++){
ans[i]=g[i];for(int j:S[i]) if(j^fa[i]) ans[i]+=f[j];
printf("%lld ",ans[i]);
}
}
int main(){
int t=1;
// scanf("%d",&t);
while(t--) Solve();
cerr<<clock()*1.0/CLOCKS_PER_SEC<<'\n';
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 31660kb
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: 0ms
memory: 31752kb
input:
2 1 2 1 1 2
output:
1 1
result:
ok single line: '1 1 '
Test #3:
score: 0
Accepted
time: 894ms
memory: 38272kb
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 34048 34070 34152 33992 33977 34077 42219 34103 33976 34065 34170 34072 34061 34069 34177 34068 34129 33872 50478 34059 33921 34153 34049 34034 33820 34132 34116 34361 33728 50043 34138 33855 33873 34309 34319 34068 50753 34135 34256 34159 34034 34056 34361 34171 34316 34058 34125 34019 34182 ...
result:
ok single line: '34355 34048 34070 34152 33992 ... 34333 33814 33294 34266 34337 '
Test #4:
score: -100
Time Limit Exceeded
input:
65536 44501 44259 59772 51161 51582 2027 2699 8610 5021 57211 60597 10270 29222 11423 38503 3833 52021 47503 47160 15296 61201 13465 20807 17239 7705 20234 32708 25663 7800 42265 29410 44963 32173 38920 49438 61282 25922 4342 40171 9819 12256 3995 41600 39383 57051 60932 44275 8351 8356 8295 3557 64...