首页 > 代码库 > 3563: DZY Loves Chinese - BZOJ
3563: DZY Loves Chinese - BZOJ
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
为了体现在线,K以及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
2 7 0 3
6 0 7 4 6
1 2 7
0 5 0 2 13
Sample Output
Connected
Connected
Connected
Connected
Disconnected
HINT
HINT
N≤100000 M≤500000 Q≤50000 1≤K≤15
数据保证没有重边与自环
Tip:请学会使用搜索引擎
无聊写了这道伪在线题
因为我们通过计算这一行有多少个数字可以得到每次的k,xor之后得到以前说联通的次数,最后一个暴力并查集就行了
1 const 2 maxn=100100; 3 maxm=500500; 4 var 5 x,y,e:array[0..maxm]of longint; 6 f:array[0..maxn]of longint; 7 n,m,q,last:longint; 8 9 function find(x:longint):longint;10 begin11 if f[x]=x then exit(x);12 f[x]:=find(f[x]);13 exit(f[x]);14 end;15 16 procedure main;17 var18 i,cnt,k:longint;19 begin20 read(n,m);21 for i:=1 to m do22 read(x[i],y[i]);23 readln(q);readln;24 for i:=1 to q-1 do25 begin26 read(k);cnt:=0;27 while not seekeoln do28 begin29 inc(cnt);30 read(e[cnt]);31 end;32 readln;33 k:=k xor cnt;34 if k>last then35 writeln(‘Connected‘)36 else37 writeln(‘Disconnected‘);38 last:=k;39 end;40 for i:=1 to cnt do e[i]:=e[i] xor k;41 for i:=1 to n do f[i]:=i;42 for i:=1 to cnt do y[e[i]]:=x[e[i]];43 for i:=1 to m do44 if find(x[i])<>find(y[i]) then f[f[x[i]]]:=f[y[i]];45 for i:=1 to n-1 do46 if find(i)<>find(i+1) then47 begin48 writeln(‘Disconnected‘);49 exit;50 end;51 writeln(‘Connected‘);52 end;53 54 begin55 main;56 end.
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。