BZOJ 3563 DZY Loves Chinese

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\)个编号\(c_{1} \sim c_{K}\):表示\(K\)条边,编号为\(c_{1} \sim c_{K}\)。

为了体现在线,K以及\(c_{1} \sim c_{K}\)均需异或之前回答为连通的个数。

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

\(N \le 100000,M \le 500000,Q \le 50000,1 \le K \le 15\)

数据保证没有重边与自环

逗比题,考验语文能力。由于\(K\)也异或了答案,我们只要看读了几条边就可知道答案了。 呵呵,我还写的正解(见BZOJ 3569 DZY Loves Chinese II)。。。

#include<vector>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<iostream>
using namespace std; #define maxn (100010)
#define maxm (1000010)
int K,n,m,father[maxn],bit[maxn],dep[maxn],ans;
int side[maxn],next[maxm*2],toit[maxm*2],num = 1,up[maxn];
bool exist[maxm],sign; vector <int> ch[maxn]; inline int getint()
{
int x=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
return x*f;
} inline void add(int a,int b) { next[++num] = side[a]; side[a] = num; toit[num] = b; } inline void ins(int a,int b) { add(a,b); add(b,a); } struct node
{
int u,v,w;
inline void read() { u = getint(),v = getint(); ins(u,v); }
}edge[maxm]; inline int find(int a) { if (father[a] != a) father[a] = find(father[a]); return father[a]; } inline void dfs(int now,int fa)
{
for (int i = side[now];i;i = next[i])
{
if (toit[i] == fa||!exist[i>>1]) continue;
up[toit[i]] = i,ch[now].push_back(toit[i]),dep[toit[i]] = dep[now]+1,dfs(toit[i],now);
}
} inline void deal(int a,int b,int w)
{
if (dep[a] < dep[b]) swap(a,b);
while (dep[a] != dep[b])
{
edge[up[a]>>1].w ^= w;
a = toit[up[a]^1];
}
if (a == b) return;
while (a != b)
{
edge[up[a]>>1].w ^= w;
a = toit[up[a]^1];
edge[up[b]>>1].w ^= w;
b = toit[up[b]^1];
}
} inline void ready()
{
for (int i = 1;i <= n;++i) father[i] = i;
int cnt = 0;
for (int i = 1;i <= m;++i)
{
int r1 = find(edge[i].u),r2 = find(edge[i].v);
if (r1 != r2) ++cnt,father[r1] = r2,exist[i] = true;
if (cnt == n-1) break;
}
dfs(1,0);
for (int i = 1;i <= m;++i) if (!exist[i]) edge[i].w = rand()%(1<<30),deal(edge[i].u,edge[i].v,edge[i].w);
} inline bool connect()
{
int now = 1;
for (int i = 29;i >= 0&&now <= K;--i)
{
for (int j = now;j <= K;++j)
if (bit[j] & (1<<i))
{
swap(bit[now],bit[j]);
break;
}
if (bit[now]&(1<<i))
{
for (int j = 1;j <= K;++j)
if (j != now&&(bit[j]&(1<<i))) bit[j] ^= bit[now];
++now;
}
}
for (int i = 1;i <= K;++i) if (!bit[i]) return false;
return true;
} int main()
{
freopen("3563.in","r",stdin);
freopen("3563.out","w",stdout);
srand(19980402);
n = getint(),m = getint();
for (int i = 1;i <= m;++i) edge[i].read();
ready();
int Q = getint();
while (Q--)
{
K = getint(); K ^= ans;
for (int i = 1;i <= K;++i)
{
int a = getint(); a ^= ans;
bit[i] = edge[a].w;
}
sign = connect();
if (sign) puts("Connected");
else puts("Disconnected");
ans += sign;
}
return 0;
}
上一篇:Graph-BFS-图的广度优先遍历


下一篇:LPC1768的IIS通讯