QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#227626#7610. Bus Lines275307894aWA 396ms31284kbC++143.8kb2023-10-27 20:08:412023-10-27 20:08:41

Judging History

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

  • [2023-10-27 20:08:41]
  • 评测
  • 测评结果:WA
  • 用时:396ms
  • 内存:31284kb
  • [2023-10-27 20:08:41]
  • 提交

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],sum[N];int up[N];
int Rt[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;
		if(x<=l&&r<=y) return op?Sum[v]:f[v];int m=l+r>>1;
		return (x<=m?qry(x,y,op|g[v],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);
	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);
	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: 24428kb

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: 18192kb

input:

2
1 2
1
1 2

output:

1 1 

result:

ok single line: '1 1 '

Test #3:

score: -100
Wrong Answer
time: 396ms
memory: 31284kb

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:

34401 34159 34148 34211 34128 34119 34181 43091 34201 34122 34163 34218 34177 34146 34174 34220 34165 34206 34089 50556 34140 34083 34220 34160 34149 34062 34194 34192 34410 34029 50362 34200 34071 34096 34368 34375 34154 50789 34200 34339 34211 34139 34139 34405 34223 34375 34159 34196 34120 34226 ...

result:

wrong answer 1st lines differ - expected: '34355 34048 34070 34152 33992 ...5 34333 33814 33294 34266 34337', found: '34401 34159 34148 34211 34128 ... 34385 34039 33862 34347 34391 '