結果

問題 No.483 マッチ並べ
ユーザー Guowen Rong
提出日時 2025-01-27 18:45:27
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 4 ms / 2,000 ms
コード長 2,288 bytes
コンパイル時間 1,998 ms
コンパイル使用メモリ 167,536 KB
実行使用メモリ 5,760 KB
最終ジャッジ日時 2025-01-27 18:45:31
合計ジャッジ時間 3,983 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 53
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include<bits/stdc++.h>
#define lowbit(x) x & (-x)
#define pi pair<ll, ll>
#define ls(k) k << 1
#define rs(k) k << 1 | 1
#define fi first
#define se second
using namespace std;
typedef __int128 __;
typedef long double lb;
typedef double db;
typedef unsigned long long ull;
typedef long long ll;
const int N = 205;
inline ll read(){
    ll x = 0, f = 1;
    char c = getchar();
    while(c < '0' || c > '9'){
        if(c == '-')
          f = -1;
        c = getchar();
    }
    while(c >= '0' && c <= '9'){
        x = (x << 1) + (x << 3) + (c ^ 48);
        c = getchar();
    }
    return x * f;
}
inline void write(ll x){
	if(x < 0){
		putchar('-');
		x = -x;
	}
	if(x > 9)
	  write(x / 10);
	putchar(x % 10 + '0');
}
int T, n, a, b, c, d, cnt, top, ccnt;
int A[N], B[N], C[N], D[N], dfn[N], low[N], stk[N], scc[N];
bool f[N];
vector<int> V1[N][N], V2[N][N];
vector<int> E[N];
inline void add(int u, int v){
	E[u].push_back(v);
}
inline void tarjan(int u){
	dfn[u] = low[u] = ++cnt;
	f[u] = 1;
	stk[++top] = u;
	for(auto v : E[u]){
		if(!dfn[v]){
			tarjan(v);
			low[u] = min(low[u], low[v]);
		}
		else if(f[v])
		  low[u] = min(low[u], dfn[v]);
	}
	if(dfn[u] == low[u]){
		++ccnt;
		while(top){
			int x = stk[top--];
			scc[x] = ccnt;
			f[x] = 0;
			if(x == u)
			  break;
		}
	}
}
inline void solve(){
	cnt = top = ccnt = 0;
	for(int i = 0; i < N; ++i){
		E[i].clear();
		dfn[i] = low[i] = stk[i] = scc[i] = f[i] = 0;
	}
	for(int i = 0; i < N; ++i)
	  for(int j = 0; j < N; ++j)
	    V1[i][j].clear(), V2[i][j].clear();
	n = read();
	for(int i = 1; i <= n; ++i){
		a = read(), b = read(), c = read(), d = read();
		V1[a][b].push_back(i);
		V2[c][d].push_back(i);
		A[i] = a, B[i] = b, C[i] = c, D[i] = d;
	}
	for(int i = 1; i <= n; ++i){
		for(auto v : V1[A[i]][B[i]])
		  if(i != v)
		    add(i, v + n);
		for(auto v : V2[A[i]][B[i]])
		  add(i, v);
		for(auto v : V1[C[i]][D[i]])
		  add(i + n, v + n);
		for(auto v : V2[C[i]][D[i]])
		  if(i != v)
		    add(i + n, v);
	}
	for(int i = 1; i <= 2 * n; ++i)
	  if(!dfn[i])
	    tarjan(i);
	for(int i = 1; i <= n; ++i){
		if(scc[i] == scc[i + n]){
			puts("NO");
			return ;
		}
	}
	puts("YES");
}
int main(){
//	freopen("match.in", "r", stdin);
//	freopen("match.out", "w", stdout);
	T = 1;
	while(T--)
	  solve();
	return 0;
}
0