QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#227727#7610. Bus Lines275307894aWA 3ms34788kbC++144.3kb2023-10-27 22:10:152023-10-27 22:10:15

Judging History

你现在查看的是最新测评结果

  • [2023-10-27 22:10:15]
  • 评测
  • 测评结果:WA
  • 用时:3ms
  • 内存:34788kb
  • [2023-10-27 22:10:15]
  • 提交

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 '