注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

Yavin(某沙茶的代码库)

Star Wars fan and OIer

 
 
 

日志

 
 

spoj cot3 主席的题目  

2013-03-23 15:17:49|  分类: 默认分类 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
做这道题的原因是最近不是出了道线段树合并吗?
于是感到很是奇葩。。。在加上当时冬令营上听主席讲了之后就感到非常感兴趣
题解就免了吧。毕竟主席的已经讲得很清楚了。
这题我写了一会,然后卡了一会常数,加了个莫名的优化,于是就过了。
讲讲我为了卡常数干的事情吧(应该只有我的渣代码才需卡常数吧。。。)
将vector数组改成了邻接表。
将把一个数进行二进制反转操作别用vector而是用位运算(只有我这个傻叉才会这么做吧)
然后将线段树用数组实现。
将两颗线段树合并时,如果有一边已经满了,就不用管另一边直接返回(不知为何不加这个会WA?)

然后竟然在SPOJ上排到了best solution??
不过做过这道题的人本来就不多囧

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<fstream>
#include<map>
#include<ctime>
#include<set>
#include<queue>
#include<cmath>
#include<vector>
#include<bitset>
#include<functional>
#define x first
#define y second
#define mp make_pair
#define pb push_back
#define REP(i,l,r) for((i)=(l);(i)<=(r);++(i))
#define REP2(i,l,r) for((i)=(l);(i)!=(r);++(i))
using namespace std;

typedef long long LL;
typedef double ld;

const int MAX=330000+10;
const int NUM=40;

int n,len;
int color[MAX],dp[MAX],all[MAX];
int head[MAX],next[MAX],t[MAX],top;
int que[MAX],tot,father[MAX];

void add(int u,int v)
{
t[++top]=v;
next[top]=head[u];
head[u]=top;
}

void dfs(int u,int fa)
{
que[++tot]=u;
int i,v;
for(i=head[u];i!=0;i=next[i])
{
v=t[i];
if(v!=fa)
{
father[v]=u;
dfs(v,u);
}
}
}

const int SIZE_TREE=MAX*NUM;
int lc[SIZE_TREE],rc[SIZE_TREE],delta[SIZE_TREE];
bool full[SIZE_TREE];

int cnt;
int root[MAX];

int newnode()
{
return ++cnt;
}

inline void addDelta(int& v,int& de)
{
if(v)
delta[v]^=de;
}

void doit(int u)
{
if(delta[u])
{
if(delta[u]&1)
swap(lc[u],rc[u]);
int nd=delta[u]>>1;
addDelta(lc[u],nd);
addDelta(rc[u],nd);
delta[u]=0;
}
}

#define update(u) full[(u)]=full[lc[(u)]] && full[rc[(u)]]

int merge(int u,int v)
{
if(!v || full[u])return u;
if(!u || full[v])return v;
doit(u);
doit(v);
int now=newnode();
lc[now]=merge(lc[u],lc[v]);
rc[now]=merge(rc[u],rc[v]);
update(now);
return now;
}

int add(int u,int T,int res)
{
int nu=newnode();
if(u)
{
doit(u);
lc[nu]=lc[u];
rc[nu]=rc[u];
}
if(!res)
{
full[nu]=1;
return nu;
}
if(T&1)
rc[nu]=add(rc[u],T>>1,res-1);
else lc[nu]=add(lc[u],T>>1,res-1);
update(nu);
return nu;
}

int ask(int u,int l,int r)
{
if(l==r)
return l;
doit(u);
int mid=(l+r)/2;
if(!full[lc[u]])
return ask(lc[u],l,mid);
else
return ask(rc[u],mid+1,r);
}

int rev(int u)
{
int ans=0,i;
REP2(i,0,len)
ans=(ans<<1)+((u>>i)&1);
return ans;
}

void work(int u)
{
int i,v;
int all_son=0;
root[u]=newnode();
for(i=head[u];i!=0;i=next[i])
{
v=t[i];
if(father[v]==u)
all_son^=dp[v];
}
all[u]=all_son;
for(i=head[u];i!=0;i=next[i])
{
v=t[i];
if(father[v]==u)
{
delta[root[v]]^=rev(all_son^dp[v]);
root[u]=merge(root[u],root[v]);
}
}
if(color[u]==0)
root[u]=add(root[u],rev(all_son),len);
dp[u]=ask(root[u],0,(1<<len)-1);
}

int fup[MAX];
char pp[MAX];

int main()
{
#ifndef ONLINE_JUDGE
freopen("input.txt","r",stdin);freopen("output.txt","w",stdout);
#endif
int i,a,b,j;
scanf("%d\n",&n);
while((1<<len)<=n)
++len;
gets(pp);
REP(i,1,n)
color[i]=pp[2*i-2]-'0';
REP(i,1,n-1)
{
scanf("%d%d",&a,&b);
add(a,b);
add(b,a);
}
dfs(1,0);
for(i=n;i>=1;--i)
work(que[i]);
vector<int> ans;
REP(i,1,n)
{
int u=que[i];
for(j=head[u];j!=0;j=next[j])
{
int v=t[j];
if(father[v]==u)
fup[v]^=all[u]^dp[v]^fup[u];
}
if((fup[u]^all[u])==0 && color[u]==0)
ans.pb(u);
}
sort(ans.begin(),ans.end());
if(!ans.size())
cout<<-1<<endl;
else
{
REP2(i,0,ans.size())
printf("%d\n",ans[i]);
}
return 0;
}




  评论这张
 
阅读(636)| 评论(0)
推荐 转载

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017