F.A.Qs Home ProblemSet Status Ranklist Contest LoginRegister
Notice:本站提供各级各类比赛备战资源(Noip提高组及以下),有意者请联系Lydsy2012@163.com,仅限教师及家长用户。
大视野在线测评-欢迎您
[ New Thread ]
Problem 3435 >> 为何本地过编译,交上去CE
ysy20021208 @ 2019-03-29 10:55:27
[ Quote ] [ Edit ] [ Delete ] 1#
#include <queue>
#include <vector>
#include <cstdio>
#include <algorithm>
using namespace std;
#define N 100010
#define M 15000000
#define alpha 0.86
#define mod 1000000000
#define O2 __attribute__((optimize("-O2")))
vector <int> point[N],Rebuild,Rebuild2;int q[M];long long l,r; int cnt;
int n,f[18][N<<1],size[N],mx[N],fa[N],level[N],root2[N],root3[N],sum[N],all,root;
int head[N],to[N<<1],nxt[N<<1],idx;bool vis[N]; long long ans,dep[N],R[N];
struct Goat {int son[2],sum,size;long long num;}goat[M];
O2 inline int getlca(int x,int y)
{
if(level[x]>level[y]) swap(x,y);
for(register int i=17;~i;i--) if((1<<i)<=level[y]-level[x])
y=f[i][y];
if(x==y) return x;
for(register int i=17;~i;i--) if(f[i][x]!=f[i][y])
x=f[i][x],y=f[i][y];
return f[0][x];
}
O2 inline long long getdis(int x,int y) {return dep[x]+dep[y]-2*dep[getlca(x,y)];}
O2 inline void add(int a,int b) {nxt[++idx]=head[a],to[idx]=b,head[a]=idx;}
O2 inline int find(int p,long long x)
{
if(!p) return 0;/* printf("XX:: %d %lld %lld %d\n",p,goat[p].num,x,goat[p].sum);*/
if(goat[p].num>x) return find(goat[p].son[0],x);
if(goat[p].num==x) return goat[goat[p].son[0]].sum+goat[p].size;
return goat[goat[p].son[0]].sum+goat[p].size+find(goat[p].son[1],x);
}
O2 inline void pushup(int p) {goat[p].sum=goat[p].size+goat[goat[p].son[0]].sum+goat[goat[p].son[1]].sum;}
O2 inline int rebuild(int l,int r)
{
int mid=(l+r)>>1,p=Rebuild[mid];
goat[p].son[0]=goat[p].son[1]=goat[p].sum=0;
if(l!=mid) goat[p].son[0]=rebuild(l,mid-1);
if(r!=mid) goat[p].son[1]=rebuild(mid+1,r);
pushup(p); return p;
}
O2 inline void dfs(int p) {if(!p) return; dfs(goat[p].son[0]),Rebuild.push_back(p),dfs(goat[p].son[1]);}
O2 inline int newcode()
{
int p=q[(l++)%M];
if(goat[p].son[0]) q[(r++)%M]=goat[p].son[0],goat[p].son[0]=0;
if(goat[p].son[1]) q[(r++)%M]=goat[p].son[1],goat[p].son[1]=0;
goat[p].size=goat[p].sum=0; return p;
}
O2 inline void insert(int &p,long long x)
{
if(!p) p=newcode(),goat[p].num=x;goat[p].sum++;
if(goat[p].num==x) {goat[p].size++;return;}
insert(goat[p].son[goat[p].num<x],x);
if(1.0*max(goat[goat[p].son[0]].sum,goat[goat[p].son[1]].sum)>1.0*goat[p].sum*alpha)
dfs(p),p=rebuild(0,Rebuild.size()-1),Rebuild.clear();
}
ysy20021208 @ 2019-03-29 10:55:30
[ Quote ] [ Edit ] [ Delete ] 2#

O2 inline void getsize(int p,int from)
{
size[p]=1;
for(register int i=head[p];i;i=nxt[i]) if(to[i]!=from&&(!vis[to[i]]))
getsize(to[i],p),size[p]+=size[to[i]];
}
O2 inline void getroot(int p,int from)
{
mx[p]=0,size[p]=1;
for(register int i=head[p];i;i=nxt[i])
if(to[i]!=from&&(!vis[to[i]])) getroot(to[i],p),
size[p]+=size[to[i]],mx[p]=max(mx[p],size[to[i]]);
mx[p]=max(mx[p],all-size[p]);
if(mx[p]<mx[root]) root=p;
}
O2 inline void dfs2(int p,int from)
{
vis[p]=true,getsize(p,from),sum[p]=root2[p]=root3[p]=0,point[p].clear();
for(register int i=head[p];i;i=nxt[i]) if(!vis[to[i]])
root=0,all=size[to[i]],getroot(to[i],0),fa[root]=p,dfs2(root,0);
}
O2 inline void tree_rebuild(int p)
{
// printf("T: %d\n",p);
for(register int i=0;i<(int)point[p].size();i++)
vis[point[p][i]]=false,sum[point[p][i]]=0,q[(r++)%M]=root2[point[p][i]],q[(r++)%M]=root3[point[p][i]];
int tmp=fa[p];
for(register int i=0;i<(int)point[p].size();i++) Rebuild2.push_back(point[p][i]),root2[point[p][i]]=0;
// for(register int i=0;i<(int)Rebuild2.size();i++) printf("%d ",Rebuild2[i]); printf("\n");
root=0,all=(int)Rebuild2.size(),getroot(p,0),fa[root]=tmp,dfs2(root,0);
// for(register int i=0;i<(int)Rebuild2.size();i++) printf("%d ",fa[Rebuild2[i]]); printf("\n");
// for(register int i=0;i<(int)Rebuild2.size();i++) printf("%d ",root2[Rebuild2[i]]); printf("\n");
// for(register int i=0;i<(int)Rebuild2.size();i++) printf("%d ",root3[Rebuild2[i]]); printf("\n");
for(register int i=0;i<(int)Rebuild2.size();i++)
for(int j=Rebuild2[i];j!=tmp;j=fa[j])
{
// printf("%d %d %lld %d\n",j,Rebuild2[i],getdis(Rebuild2[i],j)-R[Rebuild2[i]],R[Rebuild2[i]]);
insert(root2[j],getdis(Rebuild2[i],j)-R[Rebuild2[i]]),point[j].push_back(Rebuild2[i]);
if(fa[j]) insert(root3[j],getdis(Rebuild2[i],fa[j])-R[Rebuild2[i]]); sum[j]++;
}/* printf("%d\n",Rebuild2.size());
for(register int i=0;i<(int)Rebuild2.size();i++)
{
printf("%d\n",Rebuild2[i]);
for(int j=0;j<(int)point[Rebuild2[i]].size();j++)
printf("%d ",point[Rebuild2[i]][j]); printf("\n");
}*/
Rebuild2.clear();
}
O2 int main()
{
for(register int i=1;i<M;i++) q[(r++)%M]=i;
scanf("%d",&n),scanf("%d",&n),printf("0\n"),mx[0]=n+1;
for(register int i=1;i<=n;i++)
{
int x,y; scanf("%d%d%lld",&x,&y,&R[i]),x^=ans%mod,vis[i]=true;
// printf("%d %d\n",x,i);
if(i==1) {insert(root2[1],-R[i]),sum[1]=1,point[1].push_back(i);continue;} add(x,i),add(i,x);
fa[i]=f[0][i]=x,level[i]=level[x]+1,dep[i]=dep[x]+y;
for(int j=1;j<=17;j++) f[j][i]=f[j-1][f[j-1][i]];
for(int j=i;j;j=fa[j])
{
// printf("%lld %d %d %d %lld\n",ans,i,j,sum[j],R[i]-getdis(i,j));
ans+=find(root2[j],R[i]-getdis(i,j));/* printf("%lld\n",ans);*/
if(fa[j]) ans-=find(root3[j],R[i]-getdis(i,fa[j]));
}
for(int j=i;j;j=fa[j])
{
// printf("A\n");
insert(root2[j],getdis(i,j)-R[i]),sum[j]++,point[j].push_back(i);
if(fa[j]) insert(root3[j],getdis(i,fa[j])-R[i]);
// printf("B\n");
}
printf("%lld\n",ans);
for(int j=i;fa[j];j=fa[j]) if(1.0*sum[j]>1.0*sum[fa[j]]*alpha)
{/*printf("T\n"),*/tree_rebuild(fa[j]);break;}
}
}
[Top] [Previous Page] [Next Page]

HOME Back