社区讨论
不是,这是什么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 条回复,欢迎继续交流。
正在加载回复...