[BZOJ3569]DZY Loves Chinese II(随机化+线性基)
2024-08-27 07:50:21
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 13Sample Output
Connected
Connected
Connected
Connected
DisconnectedHINT
N≤100000 M≤500000 Q≤50000 1≤K≤15
数据保证没有重边与自环
Tip:请学会使用搜索引擎
Source
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 ;
}
最新文章
- ansible操作远程服务器报Error: ansible requires the stdlib json or simplejson module, neither was found!
- Android Activity使用拾遗
- DB层面上的设计 分库分表 读写分离 集群化 负载均衡
- 利用URLScan工具过滤URL中的特殊字符(仅针对IIS6)
- (三)CSS高级语法
- POJ3254Corn Fields(状压DP)
- VLSI和ASIC的区别(转)
- 利用反射动态构成sql语句
- Intent Flag实际项目 -- 超时跳转登录界面并清理前面所有activity
- 【NOI2005】维护数列
- 利用github协作开发步骤
- 一段充满bug的R程序,慎入 ...
- 如何给小学生讲清楚ECC椭圆曲线加密
- Python实现:汉诺塔问题
- dotnet不是内部或外部的命令,也不是可运行的程序或批处理文件
- python常用库函数 - 备忘
- SD从零开始64-特异的业务交易(Special Business Transactions)
- ncodeURIComponent() 函数 vue内容
- Socket编程 - 网络基础知识
- Java并发:volatile内存可见性和指令重排