結果

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

ソースコード

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; cin>>t;
    while(t--) solve();
    return 0;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0