QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#227727 | #7610. Bus Lines | 275307894a | WA | 3ms | 34788kb | C++14 | 4.3kb | 2023-10-27 22:10:15 | 2023-10-27 22:10:15 |
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*16+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];
struct node{int x,y,ti;};
vector<node> Q[N];vector<pair<int,int> > D[N];
namespace Tree{
#define ls v<<1
#define rs v<<1|1
int lim;void BD(){lim=1<<__lg(n+5)+1;}
int g[M],flag[M];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){flag[v]=1;g[v]+=w;Up(v);}
void Add(int x,int y,int w,int l=0,int r=lim-1,int v=1){
x--;y++;x+=lim;y+=lim;
while(x^y^1) {
if(!(x&1)) PF(x^1,w);if(y&1) PF(y^1,w);
x>>=1;y>>=1;Up(x);Up(y);flag[x]=flag[y]=1;
}
while(x^1) x>>=1,Up(x);
// 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 clr(int l=0,int r=lim-1,int v=1){
if(!flag[v]) return;flag[v]=g[v]=0;if(l==r) return;
int m=l+r>>1;clr(l,m,ls);clr(m+1,r,rs);
}
void modify(int x,ll w,int l=0,int r=lim-1,int v=1){
Sum[v]+=w;if(l==r) return Up(v);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=0,int r=lim-1,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 YAI;
int MIN(int x,int y){return d[x]<d[y]?x:y;}
void ins(int x,int La,int w,int ti){
if(w==-1) return Tree::clr();
for(auto i:Q[x]) if(i.ti<ti) Tree::Add(i.x,i.y,w),YAI++;
for(int i:S[x]) if(i^La) ins(i,x,w,ti);
}
void dfs3(int x,int La){
for(int i:S[x]) if(i^La) dfs3(i,x);
for(auto i:Q[x]) Tree::Add(i.x,i.y,1);
for(auto i:D[x]) Tree::Add(i.fi,i.se,-2);
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,d[i]);
if(Sn[x]) dfs4(Sn[x],x);
for(int i:S[x]) if(i^La&&i^Sn[x]) ins(i,x,1,d[i]);
for(auto i:Q[x]) Tree::Add(i.x,i.y,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);
}
Tree::BD();
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((node){i.fi,i.se,d[Ls]}),Q[y].eb((node){i.fi,i.se,d[Ls]}),D[Ls].eb(i);
}
dfs3(Rt,0);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]);
}
cerr<<YAI<<'\n';
}
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: 0
Wrong Answer
time: 3ms
memory: 34788kb
input:
6 1 2 5 4 6 5 3 1 1 5 3 6 1 2 3 6 4
output:
6 9 9 0 5 5
result:
wrong answer 1st lines differ - expected: '6 9 9 10 7 7', found: '6 9 9 0 5 5 '