3569: DZY Loves Chinese II

Time Limit: 5 Sec  Memory Limit: 64 MB
Submit: 1515  Solved: 569
[Submit][Status][Discuss]

Description

神校XJ之学霸兮,Dzy皇考曰JC。
摄提贞于孟陬兮,惟庚寅Dzy以降。
纷Dzy既有此内美兮,又重之以修能。
遂降临于OI界,欲以神力而凌♂辱众生。
 
今Dzy有一魞歄图,其上有N座祭坛,又有M条膴蠁边。
时而Dzy狂WA而怒发冲冠,神力外溢,遂有K条膴蠁边灰飞烟灭。
而后俟其日A50题则又令其复原。(可视为立即复原)
然若有祭坛无法相互到达,Dzy之神力便会大减,于是欲知其是否连通。

Input

第一行N,M
接下来M行x,y:表示M条膴蠁边,依次编号
接下来一行Q
接下来Q行:
每行第一个数K而后K个编号c1~cK:表示K条边,编号为c1~cK
为了体现在线,c1~cK均需异或之前回答为连通的个数

Output

对于每个询问输出:连通则为‘Connected’,不连通则为‘Disconnected’
(不加引号)

Sample Input

5 10
2 1
3 2
4 2
5 1
5 3
4 1
4 3
5 2
3 1
5 4
5
1 1
3 7 0 3
4 0 7 4 6
2 2 7
4 5 0 2 13

Sample Output

Connected
Connected
Connected
Connected
Disconnected

HINT

N≤100000 M≤500000 Q≤50000 1≤K≤15

数据保证没有重边与自环

Tip:请学会使用搜索引擎

Source

[Submit][Status][Discuss]

BZOJ3237的强制在线版,卡掉了CDQ分治。

有一种很神的随机化,配合线性基解决。

 #include<cstdio>
#include<cstring>
#include<algorithm>
#include<cstdlib>
#define rep(i,l,r) for (int i=l; i<=r; i++)
#define For(i,x) for (int i=h[x],k; i; i=nxt[i])
typedef long long ll;
using namespace std; const int N=,M=,SS=;
int n,m,Q,cnt=,u,v,x,k,ans,h[N],nxt[M],to[M],val[N],fa[N],a[];
bool vis[N],use[M];
struct E{ int x,y,v; }e[M];
void add(int u,int v){ nxt[++cnt]=h[u]; h[u]=cnt; to[cnt]=v; } void dfs(int x,int f){
vis[x]=;
For(i,x) if ((k=to[i])!=f && !vis[k]) use[i>>]=,fa[k]=x,dfs(k,x);
} void dfs2(int x){
For(i,x) if (fa[k=to[i]]==x)
dfs2(k),e[i>>].v^=val[k],val[x]^=val[k];
} int main(){
freopen("bzoj3569.in","r",stdin);
freopen("bzoj3569.out","w",stdout);
scanf("%d%d",&n,&m); srand();
rep(i,,m) scanf("%d%d",&e[i].x,&e[i].y),add(e[i].x,e[i].y),add(e[i].y,e[i].x);
dfs(,);
rep(i,,m) if (!use[i]) x=rand()%SS+,e[i].v=x,val[e[i].x]^=x,val[e[i].y]^=x;
dfs2(); scanf("%d",&Q);
while (Q--){
scanf("%d",&k); memset(a,,sizeof(a)); bool f=;
rep(i,,k){
scanf("%d",&x); x^=ans; x=e[x].v;
for (int j=; ~j; j--){
if (!((x>>j)&)) continue;
if (!a[j]) { a[j]=x; break; }
x^=a[j];
}
if (!x) f=;
}
if (!f) puts("Disconnected"); else puts("Connected"),ans++;
}
return ;
}

最新文章

  1. ansible操作远程服务器报Error: ansible requires the stdlib json or simplejson module, neither was found!
  2. Android Activity使用拾遗
  3. DB层面上的设计 分库分表 读写分离 集群化 负载均衡
  4. 利用URLScan工具过滤URL中的特殊字符(仅针对IIS6)
  5. (三)CSS高级语法
  6. POJ3254Corn Fields(状压DP)
  7. VLSI和ASIC的区别(转)
  8. 利用反射动态构成sql语句
  9. Intent Flag实际项目 -- 超时跳转登录界面并清理前面所有activity
  10. 【NOI2005】维护数列
  11. 利用github协作开发步骤
  12. 一段充满bug的R程序,慎入 ...
  13. 如何给小学生讲清楚ECC椭圆曲线加密
  14. Python实现:汉诺塔问题
  15. dotnet不是内部或外部的命令,也不是可运行的程序或批处理文件
  16. python常用库函数 - 备忘
  17. SD从零开始64-特异的业务交易(Special Business Transactions)
  18. ncodeURIComponent() 函数 vue内容
  19. Socket编程 - 网络基础知识
  20. Java并发:volatile内存可见性和指令重排

热门文章

  1. ssh-debian87.sh
  2. Oz 创建CentOS6镜像
  3. 简述Shiro验证过程
  4. 博客挪窝了 http://my.oschina.net/jrrx/blog
  5. [译]如何去除pandas dataframe里面的Unnamed的列?
  6. PL/SQL 查询结果集直接修改数据
  7. Codeforces Round #352 (Div. 2) C
  8. mysql外网链接
  9. hibernate用注解的方式实现orm
  10. reduce实现数组求和