社区讨论

不是,这是什么TLE?!

P5901[IOI 2009] Regions参与者 4已保存回复 7

讨论操作

快速查看讨论及其快照的属性,并进行相关操作。

当前回复
7 条
当前快照
1 份
快照标识符
@mhj0r67n
此快照首次捕获于
2025/11/03 18:50
4 个月前
此快照最后确认于
2025/11/03 18:50
4 个月前
查看原帖
绝对不可能是没刷新缓冲区,因为每一个cout后面我都加了fflush(stdout)
那么TLE 6ms 是什么鬼?!
CPP
#include<bits/stdc++.h>
using namespace std;
int n,r,q;
int B;
int h[200005],s[200005];
vector<int>g[200005];
vector<pair<int,int>>st[25005];
int mp1[500][25005],mp2[25005][500];
int cnt[25005];
int bcnt,idb[25005];
int ncnt,dfn[200005],siz[200005];
int lcnt[25005];
vector<int>lrgs;
inline void dfs(int u){
	siz[u]=1;
	dfn[u]=++ncnt;
	for(auto x:lrgs){
		mp1[idb[x]][h[u]]+=lcnt[x];
	}
	if(st[h[u]].size()>B){
		lcnt[h[u]]++;
		if(lcnt[h[u]]==1)lrgs.emplace_back(h[u]);
		for(int i=1;i<=r;i++){
			mp2[i][idb[h[u]]]+=cnt[i];
		}
	}
	cnt[h[u]]++;
	for(auto v:g[u]){
		dfs(v);
		siz[u]+=siz[v];
	}
	cnt[h[u]]--;
	if(st[h[u]].size()>B){
		lcnt[h[u]]--;
		if(lcnt[h[u]]==0)lrgs.pop_back();
	}
}
int main(){
	//freopen("1.in","r",stdin);
	//freopen("1.out","w",stdout);
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	cin>>n>>r>>q;
	B=pow(n,0.58);
	cin>>h[1];
	st[h[1]].push_back({0,1});
	for(register int i=2;i<=n;i++){
		cin>>s[i]>>h[i];
		g[s[i]].emplace_back(i);
		st[h[i]].emplace_back(0,i);
	}
	for(register int i=1;i<=r;i++){
		if(st[i].size()>B)idb[i]=++bcnt;
	}
	dfs(1);
	for(register int i=1;i<=r;i++){
		for(register int j=0;j<st[i].size();j++){
			st[i][j].first=dfn[st[i][j].second];
		}
		sort(st[i].begin(),st[i].end());
	}
	while(q--){
		int u,v;
		cin>>u>>v;
		if(st[u].size()>B){
			cout<<mp1[idb[u]][v]<<"\n";
			fflush(stdout);
		}else if(st[v].size()>B){
			cout<<mp2[u][idb[v]]<<"\n";
			fflush(stdout);
		}else{
			int sum=0,lid=0;
			for(auto x:st[u]){
				while(lid<st[v].size()&&st[v][lid]<make_pair(dfn[x.second],0))lid++;
				int rid=upper_bound(st[v].begin(),st[v].end(),make_pair(dfn[x.second]+siz[x.second]-1,n+1))-st[v].begin()-1;
				sum+=(rid-lid+1);
			}
			cout<<sum<<"\n";
			fflush(stdout);
		}
	}
}

回复

7 条回复,欢迎继续交流。

正在加载回复...