結果

問題 No.1744 Selfish Spies 1 (à la Princess' Perfectionism)
ユーザー tko919tko919
提出日時 2024-02-08 17:40:39
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 58 ms / 5,000 ms
コード長 5,499 bytes
コンパイル時間 2,726 ms
コンパイル使用メモリ 220,688 KB
実行使用メモリ 6,784 KB
最終ジャッジ日時 2024-02-08 17:40:43
合計ジャッジ時間 4,736 ms
ジャッジサーバーID
（参考情報） 		judge11 / judge15
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
6,676 KB
testcase_01 AC 2 ms
6,676 KB
testcase_02 AC 2 ms
6,676 KB
testcase_03 AC 1 ms
6,676 KB
testcase_04 AC 2 ms
6,676 KB
testcase_05 AC 2 ms
6,676 KB
testcase_06 AC 2 ms
6,676 KB
testcase_07 AC 2 ms
6,676 KB
testcase_08 AC 2 ms
6,676 KB
testcase_09 AC 2 ms
6,676 KB
testcase_10 AC 2 ms
6,676 KB
testcase_11 AC 2 ms
6,676 KB
testcase_12 AC 2 ms
6,676 KB
testcase_13 AC 2 ms
6,676 KB
testcase_14 AC 2 ms
6,676 KB
testcase_15 AC 2 ms
6,676 KB
testcase_16 AC 2 ms
6,676 KB
testcase_17 AC 4 ms
6,676 KB
testcase_18 AC 4 ms
6,676 KB
testcase_19 AC 2 ms
6,676 KB
testcase_20 AC 2 ms
6,676 KB
testcase_21 AC 2 ms
6,676 KB
testcase_22 AC 2 ms
6,676 KB
testcase_23 AC 2 ms
6,676 KB
testcase_24 AC 12 ms
6,676 KB
testcase_25 AC 3 ms
6,676 KB
testcase_26 AC 3 ms
6,676 KB
testcase_27 AC 5 ms
6,676 KB
testcase_28 AC 55 ms
6,784 KB
testcase_29 AC 5 ms
6,676 KB
testcase_30 AC 5 ms
6,676 KB
testcase_31 AC 5 ms
6,676 KB
testcase_32 AC 5 ms
6,676 KB
testcase_33 AC 55 ms
6,784 KB
testcase_34 AC 54 ms
6,784 KB
testcase_35 AC 58 ms
6,676 KB
testcase_36 AC 58 ms
6,676 KB
testcase_37 AC 57 ms
6,784 KB
testcase_38 AC 57 ms
6,784 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

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

#define rep(i,a,b) for(int i=(int)(a);i<(int)(b);i++)
#define ALL(v) (v).begin(),(v).end()
#define UNIQUE(v) sort(ALL(v)),(v).erase(unique(ALL(v)),(v).end())
#define SZ(v) (int)v.size()
#define MIN(v) *min_element(ALL(v))
#define MAX(v) *max_element(ALL(v))
#define LB(v,x) int(lower_bound(ALL(v),(x))-(v).begin())
#define UB(v,x) int(upper_bound(ALL(v),(x))-(v).begin())

using ll=long long int;
using ull=unsigned long long;
using i128=__int128_t;
using u128=__uint128_t;
const int inf = 0x3fffffff;
const ll INF = 0x1fffffffffffffff;

template<typename T>inline bool chmax(T& a,T b){if(a<b){a=b;return 1;}return 0;}
template<typename T>inline bool chmin(T& a,T b){if(a>b){a=b;return 1;}return 0;}
template<typename T,typename U>T ceil(T x,U y){assert(y!=0); if(y<0)x=-x,y=-y; return (x>0?(x+y-1)/y:x/y);}
template<typename T,typename U>T floor(T x,U y){assert(y!=0); if(y<0)x=-x,y=-y; return (x>0?x/y:(x-y+1)/y);}
template<typename T>int popcnt(T x){return __builtin_popcountll(x);}
template<typename T>int topbit(T x){return (x==0?-1:63-__builtin_clzll(x));}
template<typename T>int lowbit(T x){return (x==0?-1:__builtin_ctzll(x));}

vector<int> BiMatching(int n,int m,vector<vector<int>>& g){
    vector<int> L(n,-1),R(m,-1);
    for(;;){
        vector<int> par(n,-1),root(n,-1);
        queue<int> que;
        rep(i,0,n)if(L[i]==-1){
            que.push(i);
            root[i]=i;
        }
        bool upd=0;
        while(!que.empty()){
            int v=que.front();
            que.pop();
            if(L[root[v]]!=-1)continue;
            for(auto u:g[v]){
                if(R[u]==-1){
                    while(u!=-1){
                        R[u]=v;
                        swap(L[v],u);
                        v=par[v];
                    }
                    upd=1;
                    break;
                }
                int to=R[u];
                if(par[to]==-1){
                    root[to]=root[v];
                    par[to]=v;
                    que.push(to);
                }
            }
        }
        if(!upd)break;
    }
    return L;
}
struct SCC{
    int n,m,cur;
    vector<vector<int>> g;
    vector<int> low,ord,id;
    SCC(int _n=0):n(_n),m(0),cur(0),g(_n),low(_n),ord(_n,-1),id(_n){}
    void resize(int _n){
        n=_n;
        g.resize(n);
        low.resize(n);
        ord.resize(n,-1);
        id.resize(n);
    }
    void add_edge(int u,int v){g[u].emplace_back(v);}
    void dfs(int v,vector<int>& used){
        ord[v]=low[v]=cur++;
        used.emplace_back(v);
        for(auto& nxt:g[v]){
            if(ord[nxt]==-1){
                dfs(nxt,used); chmin(low[v],low[nxt]);
            }
            else{
                chmin(low[v],ord[nxt]);
            }
        }
        if(ord[v]==low[v]){
            while(1){
                int add=used.back(); used.pop_back();
                ord[add]=n; id[add]=m;
                if(v==add)break;
            }
            m++;
        }
    }
    void run(){
        vector<int> used;
        rep(v,0,n)if(ord[v]==-1)dfs(v,used);
        for(auto& x:id)x=m-1-x;
    }
};


#define debug(var)  do{std::cerr << #var << " : ";view(var);}while(0)
template<typename T> void view(T e){std::cerr << e << std::endl;}
template<typename T> void view(const std::vector<T>& v){for(const auto& e : v){ std::cerr << e << " "; } std::cerr << std::endl;}
template<typename T> void view(const std::vector<std::vector<T> >& vv){ for(const auto& v : vv){ view(v); } }


vector<vector<int>> DMdecomposition(int n,int m,vector<vector<int>>& g){
    auto L=BiMatching(n,m,g);
    vector G(n+m,vector<int>()),REV(n+m,vector<int>());
    rep(i,0,n)for(auto& j:g[i]){
        G[i].push_back(j+n);
        REV[j+n].push_back(i);
    }
    vector<int> R(m,-1);
    rep(i,0,n)if(L[i]!=-1){
        G[L[i]+n].push_back(i);
        REV[i].push_back(L[i]+n);
        R[L[i]]=i;
    }

    vector<int> V0,Vinf;
    queue<int> que;
    vector<int> used(n+m);
    rep(i,0,n)if(L[i]==-1){
        used[i]=1;
        que.push(i);
    }
    while(!que.empty()){
        int v=que.front();
        que.pop();
        Vinf.push_back(v);
        for(auto& to:G[v])if(!used[to]){
            used[to]=1;
            que.push(to);
        }
    }
    rep(i,0,m)if(R[i]==-1){
        used[i+n]=1;
        que.push(i+n);
    }
    while(!que.empty()){
        int v=que.front();
        que.pop();
        V0.push_back(v);
        for(auto& to:REV[v])if(!used[to]){
            used[to]=1;
            que.push(to);
        }
    }

    SCC scc(n+m);
    rep(i,0,n+m)for(auto& to:G[i]){
        if(!used[i] and !used[to])scc.add_edge(i,to);
    }
    scc.run();
    vector group(scc.m,vector<int>());
    rep(i,0,n+m)if(!used[i])group[scc.id[i]].push_back(i);

    vector<vector<int>> ret;
    ret.push_back(V0);
    for(auto& v:group)ret.push_back(v);
    ret.push_back(Vinf);
    return ret;
}


int main(){
    int n,m,L;
    cin>>n>>m>>L;
    vector<vector<int>> g(n);
    vector<int> u(L),v(L);
    rep(i,0,L){
        cin>>u[i]>>v[i];
        u[i]--; v[i]--;
        g[u[i]].push_back(v[i]);
    }

    auto ret=DMdecomposition(n,m,g);
    vector<int> ord(n+m,-1);
    rep(i,0,SZ(ret))for(auto& v:ret[i])ord[v]=i;
    // debug(ret);

    rep(i,0,L){
        if(ord[u[i]]==ord[v[i]+n] and ord[u[i]]!=0 and ord[u[i]]!=SZ(ret)-1 and SZ(ret[ord[u[i]]])<=2){
            cout<<"No"<<'\n';
        }
        else{
            cout<<"Yes"<<'\n';
        }
    }
    return 0;
}
0