题目传送门

注意

同性必定不同色

必有一个同色异性,且不相互不喜欢

Solution

我们发现,我们问题比较大的就是如何确定性别问题。我们可以一个一个加进去,在原来已经确定了的二分图上增加新的性别关系,这个可以用线段树上二分找到。

设找到的集合为 \(S\),元素为 \(S_0,S_1,...\),那么你可以发现 \(|S|\) 只有两种情况。

1. \(|S|=1\)

这种时候说明 \(L_{L_x}=x\),所以 \(S_0\) 就是与 \(x\) 同色的。

2. \(|S|=3\)

这个时候 \(S_0,S_1,S_2\) 就是喜欢 \(x\),被 \(x\) 喜欢的,以及与 \(x\) 同色的异性的。找到与 \(x\) 同色的很简单,直接选两个出来,如果 \(Query(p)=1\) 的话就说明剩下哪一个就是与 \(x\) 同色的异性。

Code

#include "chameleon.h"#include<bits/stdc++.h>using namespace std;#define Int register int#define MAXN 1005template <typename T> inline void read (T &t){t = 0;char c = getchar();int f = 1;while (c < '0' || c > '9'){if (c == '-') f = -f;c = getchar();}while (c >= '0' && c <= '9'){t = (t << 3) + (t << 1) + c - '0';c = getchar();} t *= f;}template <typename T,typename ... Args> inline void read (T &t,Args&... args){read (t);read (args...);}template <typename T> inline void write (T x){if (x < 0){x = -x;putchar ('-');}if (x > 9) write (x / 10);putchar (x % 10 + '0');}template <typename T> inline void chkmax (T &x,T y){x = max (x,y);}template <typename T> inline void chkmin (T &x,T y){x = min (x,y);}vector <int> G[MAXN];bool b[MAXN],used[MAXN];int n,t[2][MAXN],col[MAXN],lov[MAXN],siz[2];void dfs (int x,int c){col[x] = c;for (Int to : G[x]) if (col[to] == -1) dfs (to,c ^ 1);}void getcol (int x){for (Int i = 1;i < x;++ i) col[i] = -1;for (Int i = 1;i < x;++ i) if (col[i] == -1) dfs (i,0);siz[0] = siz[1] = 0;for (Int i = 1;i < x;++ i) t[col[i]][++ siz[col[i]]] = i;}bool checkit (int c,int l,int r,int x){vector <int> S;S.clear (),S.push_back (x);for (Int i = l;i <= r;++ i) if (!b[t[c][i]]) S.push_back (t[c][i]);return Query (S) < S.size();}int findit (int c,int l,int r,int x){if (l == r) return t[c][l];int mid = (l + r) >> 1;return checkit (c,l,mid,x) ? findit (c,l,mid,x) : findit (c,mid + 1,r,x);}void makeit (int Sn){int n = Sn << 1;for (Int i = 1;i <= n;++ i){getcol (i),memset (b,0,sizeof (b));for (Int c = 0;c < 2;++ c){while (checkit (c,1,siz[c],i)){int pos = findit (c,1,siz[c],i);G[i].push_back (pos),G[pos].push_back (i),b[pos] = 1;}}}vector <int> S;S.resize (3);for (Int i = 1;i <= n;++ i){if (G[i].size() == 1){if (used[i]) continue;used[i] = used[G[i][0]] = 1,Answer (i,G[i][0]);continue;}S[0] = i,S[1] = G[i][0],S[2] = G[i][1];if (Query (S) == 1){swap (G[i][0],G[i][2]),lov[G[i][0]] = i;continue;}S[2] = G[i][2];if (Query (S) == 1){swap (G[i][0],G[i][1]),lov[G[i][0]] = i;continue;}lov[G[i][0]] = i;}for (Int i = 1;i <= n;++ i) if (!used[i]){if (lov[i] == G[i][1]) Answer (i,G[i][2]),used[i] = used[G[i][2]] = 1;else Answer (i,G[i][1]),used[i] = used[G[i][1]] = 1;} }void Solve (int N){makeit (N);}