QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#687889#4901. Speike & TomAcoipp0 859ms72080kbC++149.7kb2024-10-29 21:43:512024-10-29 21:43:52

Judging History

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

  • [2024-10-29 21:43:52]
  • 评测
  • 测评结果：0
  • 用时：859ms
  • 内存：72080kb
查看
  • [2024-10-29 21:43:51]
  • 提交

answer

#include<bits/stdc++.h>
#define ll long long
#define N 100005
using namespace std;
inline char nc(){
	static char buf[1000000],*p=buf,*q=buf;
	return p==q&&(q=(p=buf)+fread(buf,1,1000000,stdin),p==q)?EOF:*p++;
}
inline ll read(){
	ll res = 0,w = 1;
	char c = nc();
	while(c<'0'||c>'9')w=(c=='-'?-1:w),c=nc();
	while(c<='9'&&c>='0')res=res*10+c-'0',c=nc();
	return res*w;
}
char obuf[1<<21],*p3=obuf; 
inline void pc(char c){ 
	p3-obuf<=(1<<20)?(*p3++=c):(fwrite(obuf,p3-obuf,1,stdout),p3=obuf,*p3++=c); 
} 
inline void write(ll x){ 
	if(x<0) pc('-'),x=-x; 
	if(x>9) write(x/10); 
	pc(x%10+'0'); 
}
vector<ll> extra[N];
ll n,m,i,x,y,la[N],ne[N<<1],to[N<<1],et,vis[N],st[N][21],dep[N],key[N],keyboard[N],ans,col[N],tim,si[N],st_cut[N][21],st_extra[N][21],depp[N],next_root,fath[N],dis0[N],dis1[N],type[N],DIS[N],FATH[N];
vector<ll> v1,v2;
struct BIT{
	ll tr[N];
	inline void add(ll k,ll x){while(k<=n) tr[k]+=x,k+=k&(-k);}
	inline ll query(ll k){
		ll num = 0;
		while(k) num+=tr[k],k-=k&(-k);
		return num;
	}
	inline void clear(ll k){while(k<=n) tr[k]=0,k+=k&(-k);}
}tr1,tr2;
inline void merge(ll x,ll y){
	et++,ne[et]=la[x],la[x]=et,to[et]=y;
	et++,ne[et]=la[y],la[y]=et,to[et]=x;
}
inline void dfs(ll x,ll fa){
	FATH[x] = fa;
	for(ll i=1;i<=17;i++) st[x][i]=st[st[x][i-1]][i-1];
	for(ll i=la[x];i;i=ne[i]){
		if(to[i]==fa) continue;
		dep[to[i]] = dep[x]+1,st[to[i]][0] = x;
		dfs(to[i],x);
	}
}
inline void dfs2(ll x,ll fa){
	keyboard[x] = vis[x];
	for(ll i=la[x];i;i=ne[i]){
		if(to[i]==fa) continue;
		dfs2(to[i],x);
		keyboard[x] += keyboard[to[i]];
	}
}
inline ll dis11(ll x,ll y){
	ll ans = dep[x]+dep[y];
	if(dep[x]>dep[y]) swap(x,y);
	for(ll i=17;i>=0;i--) if(dep[st[y][i]]>=dep[x]) y=st[y][i];
	if(x==y) return ans-2*dep[x];
	for(ll i=17;i>=0;i--) if(st[x][i]!=st[y][i]) x=st[x][i],y=st[y][i];
	return ans-2*dep[st[x][0]];
}
inline void find_root(ll x,ll fa,ll &pos,ll &num,ll alls){
	ll now = 0;
	si[x] = 1;
	for(ll i=la[x];i;i=ne[i]){
		if(col[to[i]]!=col[x]||to[i]==fa) continue;
		find_root(to[i],x,pos,num,alls);
		si[x] += si[to[i]],now = max(now,si[to[i]]);
	}
	now = max(now,alls-si[x]);
	if(now<num) num=now,pos=x;
}
inline void init(ll x,ll fa){
	if(fa==-1) key[x]=n;
	else{
		key[x]=n;
		for(ll i=la[x];i;i=ne[i]){
			if(to[i]==fa){
				if(to[i]==FATH[x]) key[x]=keyboard[x];
				else key[x]-=keyboard[to[i]];
			}
		}
	}
	si[x] = 1,fath[x] = fa,dis0[x] = 0x3f3f3f3f,dis1[x] = 0x3f3f3f3f;
	for(ll i=la[x];i;i=ne[i]){
		if(col[to[i]]!=col[x]||to[i]==fa) continue;
		depp[to[i]] = depp[x] + 1; 
		init(to[i],x);
		si[x] += si[to[i]];
	}
}
inline void dfs_col(ll x,ll fa){
	for(ll i=la[x];i;i=ne[i]){
		if(col[to[i]]!=col[x]||to[i]==fa) continue;
		dfs_col(to[i],x);
	}
	col[x]=tim;
}
inline void dfs_insert_b(ll x,ll fa,ll delta){
	tr1.add(depp[x],delta);
	for(ll i=la[x];i;i=ne[i]) if(col[to[i]]==col[x]&&to[i]!=fa) dfs_insert_b(to[i],x,delta);
}
inline ll foundd(ll x,ll deppp){
	ll ans = 0;
	for(ll i=17;i>=0;i--) if(st_extra[x][i]&&depp[st_extra[x][i]]>deppp) x=st_extra[x][i],ans+=(1ll<<i);
	return ans+1;
}
inline bool found2(ll x,ll y){
	for(ll i=la[x];i;i=ne[i]) if(to[i]==y) return 1;
	return 0;
}
inline void dfs_find_a(ll x,ll fa,ll root){
	if(depp[x]==1) st_extra[x][0]=fa;
	else{
		st_extra[x][0]=fa;
		for(ll i=0;i<extra[x].size();i++) if(col[extra[x][i]]==col[x]&&depp[extra[x][i]]==depp[x]-2) st_extra[x][0]=extra[x][i];
	}
	for(ll i=1;i<=17;i++) st_cut[x][i]=st_cut[st_cut[x][i-1]][i-1];
	for(ll i=1;i<=17;i++) st_extra[x][i]=st_extra[st_extra[x][i-1]][i-1];
	if(key[x]){
		//Pos 作为 B 
		ans+=tr1.query(n)+1;
	}
	else{
		vector<ll> v(0);
		ll pos = x,step = -1,delta = -1;
		for(ll i=17;i>=0;i--) if(st_cut[pos][i]&&!key[st_cut[pos][i]]) pos=st_cut[pos][i];
		for(ll i=0;i<extra[pos].size();i++) if(col[extra[pos][i]]==col[pos]&&depp[extra[pos][i]]==depp[pos]&&key[extra[pos][i]]) v.push_back(extra[pos][i]);
		if(v.size()) step=foundd(x,depp[pos])+1,delta=depp[v[0]];
		else step=foundd(x,depp[st_cut[pos][0]]),delta=depp[st_cut[pos][0]];
		pos=st_cut[pos][0];
		//Pos 作为 B 
		cerr<<"pos is B when "<<step<<" "<<delta<<endl;
		if(step-delta<0) ans++;
		ans+=tr1.query(n)-tr1.query(max(0ll,step-delta));
		if(pos==root&&v.size()==1){
			next_root = v[0];
			v1.push_back(step),v2.push_back(foundd(x,pos));
		}
	}
	for(ll i=la[x];i;i=ne[i]){
		if(col[to[i]]!=col[x]||to[i]==fa) continue;
		st_cut[to[i]][0] = x;
		dfs_find_a(to[i],x,root);
	}
	for(ll i=0;i<=17;i++) st_cut[x][i]=0,st_extra[x][i]=0;
}
inline void dfss(ll x,ll fa,ll type){
	if(type==0) ans -= tr2.query(depp[x]);
	else ans += tr2.query(depp[x]-1);
	for(ll i=la[x];i;i=ne[i]) if(col[to[i]]==col[x]&&to[i]!=fa) dfss(to[i],x,type);
}
inline void dfs_find_b(ll x,ll fa,ll root){
	for(ll i=1;i<=17;i++) st_cut[x][i]=st_cut[st_cut[x][i-1]][i-1];
	dis0[x] = min(dis0[x],dis0[fa]+1),dis1[x] = min(dis1[x],dis1[fa]+1);
	for(ll i=0;i<extra[x].size();i++){
		if(col[extra[x][i]]==col[x]&&depp[extra[x][i]]==depp[x]-2){
			dis0[x] = min(dis0[x],dis0[extra[x][i]]+1);
			dis1[x] = min(dis1[x],dis1[extra[x][i]]+1);
		}
	}
	ll pos = x,cntt = key[pos];
	for(ll i=17;i>=0;i--) if(st_cut[pos][i]&&key[root]-key[st_cut[pos][i]]) pos=st_cut[pos][i];
	if(key[root]-key[st_cut[pos][i]]) pos=st_cut[pos][0];
	for(ll i=la[pos];i;i=ne[i]){
		if(to[i]==fath[pos]||col[to[i]]!=col[pos]) continue;
		cntt -= key[to[i]];
	} 
	if(cntt){
		ll temp = 0;
		for(ll i=0;i<extra[fath[pos]].size();i++) if(col[extra[fath[pos]][i]]==col[pos]&&dep[extra[fath[pos]][i]]==dep[pos]+1&&!found2(extra[fa][i],pos)) temp=1;
		if(fath[pos]!=root){
			ll step = -1,dis00 = -1,dis11 = -1;
			if(temp==0) step=depp[x]-depp[pos],dis00 = dis0[pos],dis11 = dis1[pos];
			else step=depp[x]-depp[pos]+1,dis00 = dis0[fath[pos]]+1,dis11 = dis1[fath[pos]]+1;
			//Pos 作为 A 点 
			if(step-1-dis00>=0) ans++;
			ans+=tr1.query(max(step-1-dis00,0ll));
			ans+=tr2.query(max(step-1-dis11,0ll));
		}
		else{
			ll step = -1,dis00 = -1,dis11 = -1;
			if(temp==0) step=depp[x]-depp[pos],dis00 = dis0[pos],dis11 = dis1[pos];
			else step=depp[x]-depp[pos]+1,dis00 = 1,dis11 = 1;
			//Pos 作为 A 点 
			if(step-1-dis00>=0) ans++;
			ans+=tr1.query(max(step-1-dis00,0ll));
			ans+=tr2.query(max(step-1-dis11,0ll));
		}
	}
	for(ll i=la[x];i;i=ne[i]){
		if(to[i]==fa||col[to[i]]!=col[x]) continue;
		st_cut[to[0]][0] = x;
		dfs_find_b(to[i],x,root);
	}
	for(ll i=0;i<=17;i++) st_cut[x][i]=0;
}
inline bool found(ll x,ll y){
	for(ll i=0;i<extra[x].size();i++) if(extra[x][i]==y) return 1;
	return 0;
}
inline void dfs_insert_a(ll x,ll fa){
	if(type[x]==1) tr1.add(DIS[x],1);
	if(type[x]==0) tr2.add(DIS[x],1);
	for(ll i=la[x];i;i=ne[i]){
		if(to[i]==fa||col[to[i]]!=col[x]) continue;
		if(found(to[i],fa)) DIS[to[i]]=DIS[fa],type[to[i]]=type[fa];
		else DIS[to[i]]=DIS[x],type[to[i]]=type[x];
		dfs_insert_a(to[i],x);
	}
}
inline void dfs_erase_a(ll x,ll fa){
	if(type[x]==0) tr1.add(DIS[x],1);
	if(type[x]==1) tr2.add(DIS[x],1);
	for(ll i=la[x];i;i=ne[i]){
		if(to[i]==fa||col[to[i]]!=col[x]) continue;
		dfs_erase_a(to[i],x);
	}
}
inline void solve(ll x,ll alls){
	if(alls==1) return ;
	ll pos = -1,num = LLONG_MAX,cnt_key_son = 0;
	find_root(x,-1,pos,num,alls);
	depp[pos] = 0,init(pos,-1);
	if(key[pos]==0) return ;
	for(ll i=la[pos];i;i=ne[i]) if(col[to[i]]==col[pos]&&key[to[i]]) cnt_key_son++;
	for(ll i=la[pos];i;i=ne[i]) if(col[to[i]]==col[pos]) dfs_insert_b(to[i],pos,1);
	cerr<<"! "<<pos<<endl;
	if(!(cnt_key_son==1&&!vis[pos])){
		cerr<<"type is A-P\n";
		//在 A-P 上 
		ans += (alls-1); //Pos 作为 A 点 
		for(ll i=la[pos];i;i=ne[i]){
			if(col[to[i]]==col[pos]){
				next_root = -1;
				st_cut[to[i]][0] = pos;
				dfs_insert_b(to[i],pos,-1);
				dfs_find_a(to[i],pos,pos);
				if(next_root!=-1){
					for(ll j=0;j<v1.size();j++) tr2.add(v1[j],1);
					dfss(next_root,pos,0);
					for(ll j=0;j<v1.size();j++) tr2.clear(v1[j]);
					for(ll j=0;j<v2.size();j++) tr2.add(v2[j],1);
					dfss(next_root,pos,1);
					for(ll j=0;j<v2.size();j++) tr2.clear(v2[j]);
					v1.clear(),v2.clear();
				}
				dfs_insert_b(to[i],pos,1);
			}
		}
		for(ll i=la[pos];i;i=ne[i]) if(col[to[i]]==col[pos]) dfs_insert_b(to[i],pos,-1);
	}
	else{
		cerr<<"type is B-P\n";
		//在 B-P（不包含） 上 
		for(ll i=la[pos];i;i=ne[i]){
			if(col[to[i]]==col[pos]){
				if(!key[to[i]]) continue;
				st_cut[to[i]][0] = pos;
				dfs_insert_b(to[i],pos,-1);
				dfs_find_a(to[i],pos,pos);
				dfs_insert_b(to[i],pos,1);
			}
		}
		ll root = -1;
		for(ll i=la[pos];i;i=ne[i]) if(col[to[i]]==col[pos]) dfs_insert_b(to[i],pos,-1);
		for(ll i=la[pos];i;i=ne[i]) if(col[to[i]]==col[pos]) if(key[to[i]]) root=to[i];
		for(ll i=la[pos];i;i=ne[i]){
			if(col[to[i]]==col[pos]){
				if(!key[to[i]]){
					if(found(to[i],root)) DIS[to[i]]=1,type[to[i]]=1;
					else DIS[to[i]]=1,type[to[i]]=0;
					dfs_insert_a(to[i],pos);
				}
			} 
		}
		for(ll i=la[pos];i;i=ne[i]) if(col[to[i]]==col[pos]) if(key[to[i]]) st_cut[to[i]][0]=pos,dis0[to[i]]=1,dis1[to[i]]=0,dfs_find_b(to[i],pos,pos);
		for(ll i=la[pos];i;i=ne[i]) if(col[to[i]]==col[pos]) if(!key[to[i]]) dfs_erase_a(to[i],pos);
	}
	cerr<<"root is "<<pos<<" ans is "<<ans<<endl;
	for(ll i=la[pos];i;i=ne[i]) if(col[to[i]]==col[pos]) tim++,dfs_col(to[i],pos),solve(to[i],si[to[i]]);
}
int main(){
	n=read(),m=read();
	for(i=1;i<n;i++) x=read(),y=read(),merge(x,y);
	dep[1]=1,dfs(1,-1);
	for(i=1;i<=m;i++){
		x=read(),y=read();
		ll temp = dis11(x,y);
		if(temp==1) continue;
		if(temp==2) extra[x].push_back(y),extra[y].push_back(x);
		if(temp>2) vis[x]=1,vis[y]=1;
	}
	dfs2(1,-1);
	for(i=1;i<=n;i++) cerr<<vis[i]<<" ";
	cerr<<endl;
	for(i=1;i<=n;i++) cerr<<keyboard[i]<<" ";
	cerr<<endl;
	solve(1,n);
	write(ans);
	return fwrite(obuf,p3-obuf,1,stdout),0;
}
源文件, 语言: C++14

详细

Subtask #1:

score: 0
Wrong Answer

Test #1:

score: 0
Wrong Answer
time: 0ms
memory: 26324kb

input:

20 3
1 2
1 3
3 4
4 5
1 6
6 7
1 8
5 9
8 10
5 11
7 12
11 13
12 14
11 15
4 16
7 17
2 18
1 19
3 20
8 20
12 4
10 1

output:

320

result:

wrong answer 1st numbers differ - expected: '307', found: '320'

Subtask #2:

score: 0
Skipped

Dependency #1:

0%

Subtask #3:

score: 0
Skipped

Dependency #2:

0%

Subtask #4:

score: 0
Skipped

Dependency #3:

0%

Subtask #5:

score: 0
Wrong Answer

Test #29:

score: 0
Wrong Answer
time: 859ms
memory: 72080kb

input:

98765 1
2 1
3 1
4 2
5 2
6 5
7 4
8 6
9 7
10 7
11 6
12 1
13 11
14 13
15 7
16 6
17 14
18 4
19 13
20 14
21 11
22 21
23 1
24 13
25 7
26 16
27 8
28 21
29 20
30 10
31 12
32 10
33 7
34 31
35 29
36 29
37 30
38 34
39 38
40 14
41 40
42 26
43 33
44 1
45 44
46 25
47 14
48 2
49 30
50 26
51 46
52 34
53 32
54 31
55...

output:

19788067721

result:

wrong answer 1st numbers differ - expected: '0', found: '19788067721'

Subtask #6:

score: 0
Skipped

Dependency #1:

0%
English 繁體中文 简体中文

服务器时间: 2024-12-05 06:53:33 | 开源项目