## 【Codeforces 782D】Innokenty and a Football League

### Code

2-SAT判定有没有解是可以做到$O(m)$的，写个强连通就可以了

#include<bits/stdc++.h>
#define LL long long
using namespace std;

const int N = 5000;
const int M = 5000009;

char pat[2][100];
struct Data{
char p[4];
inline bool operator < (const Data &B) const {
for (int i=0;i<3;i++) {
if (p[i] < B.p[i]) return 1;
else if (p[i] > B.p[i]) return 0;
} return 0;
}
inline bool operator == (const Data &B) const {
return !(*this < B) && !(B < *this);
}
}c1[N],c2[N];

char c=getchar(); int f=1,ret=0;
while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();}
while (c<='9'&&c>='0') {ret=ret*10+c-'0';c=getchar();}
return ret * f;
}

inline void Add_Edge(int u, int v) {
static int E = 1;
}

inline int id(int w, int t) {
return (w-1)*2 + t + 1;
}

bool DFS(int w) {
if (mark[w]) return true;
if (mark[w^1]) return false;
mark[w] = 1; que[++cnt] = w;

if (!DFS(to[i])) return false;
return true;
}

inline bool judge(){
for (int i=2,lim=id(n,2);i<=lim;i+=2) if (!mark[i] && !mark[i+1]) {
cnt = 0; if (DFS(i)) continue;
for (int j=1;j<=cnt;j++) mark[que[j]] = 0;
cnt = 0; if (!DFS(i+1)) return false;
}
return true;
}

int main() {
for (int i=1;i<=n;i++) {
scanf("%s%s",pat[0],pat[1]);
Data a; a.p[3] = 0; a.p[0] = pat[0][0]; a.p[1] = pat[0][1]; a.p[2] = pat[0][2];
Data b; b.p[3] = 0; b.p[0] = pat[0][0]; b.p[1] = pat[0][1]; b.p[2] = pat[1][0];
c1[i] = a; c2[i] = b;
}
for (int i=1;i<=n;i++) {
for (int j=1;j<=n;j++) {
if (i == j) continue;
if (c1[i] == c1[j]) Add_Edge(id(i, 2), id(j, 2));
if (c1[i] == c1[j]) Add_Edge(id(i, 1), id(j, 2));
if (c1[i] == c2[j]) Add_Edge(id(i, 1), id(j, 1));
if (c2[i] == c1[j]) Add_Edge(id(i, 2), id(j, 2));
if (c2[i] == c2[j]) Add_Edge(id(i, 2), id(j, 1));
}
}
if (!judge()) puts("NO");
else {
puts("YES");
for (int i=1;i<=n;i++) {
if (mark[id(i, 1)]) printf("%s\n",c1[i].p);
else printf("%s\n",c2[i].p);
}
}
return 0;
}


—————————— UPD 2017.3.27 ——————————

## 【BZOJ 1997】[Hnoi2010] Planar

1.圆内
2.圆外

Theorem 1. If v ≥ 3 then e ≤ 3v − 6;
Theorem 2. If v ≥ 3 and there are no cycles of length 3, then e ≤ 2v − 4.

#include<iostream>
#include<cstdio>
#include<cstring>
#include<vector>
#include<set>
#include<map>
using namespace std;

const int MAXN = 20000+9;
const int N = 200000;

vector<int> G[MAXN];
map<int,int> ins;

struct CMP{inline bool operator () (const int &A, const int &B) {return R[A] < R[B];}};
multiset<int,CMP>::iterator itr;
multiset<int,CMP> buf;

char c=getchar(); int ret=0;
while (c<'0'||c>'9'){c=getchar();}
while (c<='9'&&c>='0'){ret=ret*10+c-'0';c=getchar();}
return ret;
}

inline void init(){
for (int i=1;i<=n;i++) G[i].clear();
memset(mark,0,sizeof(mark));
}

inline void AddEdge(int a, int b) {
int ra=a*2+1, rb=b*2+1; a *= 2; b *= 2;
}

inline void build_map(){
buf.clear();
for (int i=1;i<=n;i++) {
while (buf.size() && R[*(buf.begin())] <= i) buf.erase(buf.begin());
for (int j=0,sz=G[i].size();j<sz;j++)
for (itr=buf.begin();itr!=buf.end() && R[*itr] < R[G[i][j]];itr++)
for (int j=0,sz=G[i].size();j<sz;j++) buf.insert(G[i][j]);
}
}

bool DFS(int w) {
if (mark[w]) return true;
if (mark[w^1]) return false;
mark[w] = 1; que[++cnt] = w;

if (!DFS(to[i])) return false;
return true;
}

inline bool judge(){
for (int i=2;i<=m*2+1;i+=2) if (!mark[i] && !mark[i+1]) {
cnt = 0; if (DFS(i)) continue;
for (int j=1;j<=cnt;j++) mark[que[j]] = 0;
cnt = 0; if (!DFS(i+1)) return false;
}
return true;
}

int main(){
int TT = read(); while (TT--) { init();
for (int i=1;i<=n;i++) que[i] = read(), ins[que[i]] = i;
for (int i=1;i<=m;i++) {
L[i] = ins[L[i]]; R[i] = ins[R[i]];
if (L[i] > R[i]) swap(L[i], R[i]);
G[L[i]].push_back(i);
}
if (m > 3*n-6) printf("NO\n");
else {
build_map();
if (judge()) printf("YES\n");
else printf("NO\n");
}
}
return 0;
}


## 【BZOJ 2199】[Usaco2011 Jan] 奶牛议会

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;

const int MAXN = 8000+9;

int que[MAXN],cnt,vout[MAXN],n,m;

char c=getchar(); int ret=0;
while (c<'0'||c>'9'){c=getchar();}
while (c<='9'&&c>='0'){ret=ret*10+c-'0';c=getchar();}
return ret;
}

inline void AddEdge(int u, int v){
}

inline bool DFS(int w){
if (mark[w^1]) return false;
else if (mark[w]) return true;
mark[w] = 1; que[++cnt] = w;

if (!DFS(to[i])) return false;
return true;
}

inline bool Get_Ans(){
for (int i=2;i<=n*2+1;i+=2) if (!mark[i] && !mark[i+1]) {
cnt = 0; if (DFS(i)) vout[i/2] = 1;
for (int j=1;j<=cnt;j++) mark[que[j]] = 0;
cnt = 0; if (DFS(i+1)) vout[i/2] += 2;
for (int j=1;j<=cnt;j++) mark[que[j]] = 0;
if (!vout[i/2]) return false;
}
return true;
}

int main(){
for (int i=1,a,b,ra,rb;i<=m;i++) { char tmp;
a = ra = read()*2; scanf("%c",&tmp);
if (tmp == 'Y') ra++; else a++;
b = rb = read()*2; scanf("%c",&tmp);
if (tmp == 'Y') rb++; else b++;
}
if (!Get_Ans()) printf("IMPOSSIBLE");
else for (int i=1;i<=n;i++) {
if (vout[i] == 3) printf("?");
else if (vout[i] == 1) printf("Y");
else printf("N");
}
return 0;
}


## 【BZOJ 1823】[JSOI2010] 满汉全席

2-sat的裸题

™读入那里写挫了，wa了一上午QAQ

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;

const int MAXN = 2000+9;

char pat[10];

inline char Get(){
char c=getchar();
while (c != 'm' && c != 'h') c=getchar();
return c;
}

char c=getchar(); int ret=0;
while (c<'0'||c>'9') c=getchar();
while (c<='9'&&c>='0') {ret=ret*10+c-'0';c=getchar();}
return ret;
}

inline void AddEdge(int a, int b){
}

inline void init(){
scanf("%d%d",&n,&m); T = 0;
memset(mark,0,sizeof(mark));
}

bool DFS(int w){
if (mark[w^1]) return false;
if (mark[w]) return true;
mark[w] = 1; que[++cnt] = w;

if (!DFS(to[i])) return false;
return true;
}

inline bool judge(){
for (int i=1*2;i<=n*2+1;i+=2) if (!mark[i] && !mark[i+1]) {
cnt = 0; if (DFS(i)) continue;
else {
for (int j=1;j<=cnt;j++) mark[que[j]] = 0;
cnt = 0; if (!DFS(i+1)) return false;
}
}
return true;
}

int main(){
int TT; scanf("%d",&TT);
while (TT--) {
init();
for (int i=1,a,b,ra,rb;i<=m;i++) {
pat[1] = Get(); a = ra = read()*2;
pat[4] = Get(); b = rb = read()*2;
if (pat[1] == 'm') a++; else ra++;
if (pat[4] == 'm') b++; else rb++;