結果

問題 No.483 マッチ並べ
ユーザー vjudge1
提出日時 2025-01-31 17:07:38
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
WA  
実行時間 -
コード長 1,555 bytes
コンパイル時間 1,096 ms
コンパイル使用メモリ 74,128 KB
実行使用メモリ 6,824 KB
最終ジャッジ日時 2025-01-31 17:07:42
合計ジャッジ時間 2,970 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 39 WA * 14
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include<iostream>
#include<cstdio>
#include<stack>
#include<vector>
#include<cstring>
using namespace std;
const int N=110; stack<int>sta; bool in_stack[N<<2]; vector<int>g[N<<2],hc[N][N];
int idx,scc_cnt,dfn[N<<2],low[N<<2],scc_id[N<<2];
void Tarjan(int u) {
	dfn[u]=low[u]=++idx,in_stack[u]=true,sta.push(u);
	for(auto v:g[u]) {
		if(!dfn[v]) Tarjan(v),low[u]=min(low[u],low[v]);
		else if(in_stack[v]) low[u]=min(low[u],dfn[v]);
	}
	if(dfn[u]==low[u]) {
		scc_cnt++; int v;
		do v=sta.top(),sta.pop(),in_stack[v]=false,scc_id[v]=scc_cnt; while(u!=v);
	}
}
void solve() {
	int n; cin>>n;
	for(int i=1,X1,Y1,X2,Y2;i<=n;i++) cin>>X1>>Y1>>X2>>Y2,hc[X1][Y1].push_back((i<<1)-1),hc[X2][Y2].push_back(i<<1);
	for(int i=1;i<=100;i++)
		for(int j=1;j<=100;j++)
			for(auto k:hc[i][j]) for(auto l:hc[i][j]) if(k!=l) g[k].push_back(l+(n<<1));
	for(int i=1;i<=n;i++)
		g[(i<<1)-1].push_back((i<<1)+(n<<1)),g[i<<1].push_back((i<<1)-1+(n<<1)),
		g[(i<<1)+(n<<1)].push_back((i<<1)-1),g[(i<<1)-1+(n<<1)].push_back(i<<1);
	for(int i=1;i<=(n<<2);i++) if(!dfn[i]) Tarjan(i);
	bool flag=true;
	for(int i=1;i<=(n<<1);i++) if(scc_id[i]==scc_id[i+n]) { flag=false; break; }
	cout<<(flag?"YES\n":"NO\n");
	while(!sta.empty()) sta.pop();
	idx=scc_cnt=0;
	for(int i=1;i<=(n<<2);i++) in_stack[i]=dfn[i]=low[i]=scc_id[i]=0,g[i].clear();
	for(int i=1;i<=100;i++) for(int j=1;j<=100;j++) hc[i][j].clear();
}
int main() {
	//freopen("match.in","r",stdin);
	//freopen("match.out","w",stdout);
	ios::sync_with_stdio(false),cin.tie(nullptr);
	int t=1;
	while(t--) solve();
	return 0;
}
0