結果

問題 No.1983 [Cherry 4th Tune C] 南の島のマーメイド
ユーザー t9unkubjt9unkubj
提出日時 2024-10-02 00:26:05
言語 C++23
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 413 ms / 4,000 ms
コード長 12,922 bytes
コンパイル時間 3,954 ms
コンパイル使用メモリ 282,960 KB
実行使用メモリ 29,452 KB
最終ジャッジ日時 2024-10-02 00:26:31
合計ジャッジ時間 17,166 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge5
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
5,248 KB
testcase_01 AC 2 ms
5,248 KB
testcase_02 AC 2 ms
5,248 KB
testcase_03 AC 2 ms
5,248 KB
testcase_04 AC 2 ms
5,248 KB
testcase_05 AC 2 ms
5,248 KB
testcase_06 AC 2 ms
5,248 KB
testcase_07 AC 1 ms
5,248 KB
testcase_08 AC 10 ms
5,248 KB
testcase_09 AC 14 ms
5,248 KB
testcase_10 AC 11 ms
5,248 KB
testcase_11 AC 15 ms
5,248 KB
testcase_12 AC 10 ms
5,248 KB
testcase_13 AC 236 ms
13,028 KB
testcase_14 AC 261 ms
16,340 KB
testcase_15 AC 327 ms
16,232 KB
testcase_16 AC 174 ms
10,916 KB
testcase_17 AC 257 ms
17,780 KB
testcase_18 AC 229 ms
16,220 KB
testcase_19 AC 223 ms
21,860 KB
testcase_20 AC 252 ms
15,484 KB
testcase_21 AC 234 ms
17,600 KB
testcase_22 AC 284 ms
22,432 KB
testcase_23 AC 379 ms
24,912 KB
testcase_24 AC 399 ms
24,884 KB
testcase_25 AC 389 ms
24,908 KB
testcase_26 AC 390 ms
24,764 KB
testcase_27 AC 413 ms
24,888 KB
testcase_28 AC 380 ms
24,904 KB
testcase_29 AC 379 ms
24,916 KB
testcase_30 AC 402 ms
24,760 KB
testcase_31 AC 373 ms
24,848 KB
testcase_32 AC 406 ms
24,752 KB
testcase_33 AC 2 ms
5,248 KB
testcase_34 AC 256 ms
10,448 KB
testcase_35 AC 323 ms
29,452 KB
testcase_36 AC 310 ms
20,624 KB
testcase_37 AC 2 ms
5,248 KB
testcase_38 AC 239 ms
5,248 KB
testcase_39 AC 320 ms
29,420 KB
testcase_40 AC 335 ms
23,168 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#ifdef t9unkubj
#include"template.h"
//#include"template_no_debug.h"
#else
#undef _GLIBCXX_DEBUG
#pragma GCC optimize("O3")
#define dbg(...) 199958
using namespace std;
#include<bits/stdc++.h>
using uint=unsigned;
using ll=long long;
using ull=unsigned long long;
using ld=long double;
using pii=pair<int,int>;
using pll=pair<ll,ll>;
template<class T>using vc=vector<T>;
template<class T>using vvc=vc<vc<T>>;
template<class T>using vvvc=vvc<vc<T>>;
using vi=vc<int>;
using vvi=vc<vi>;
using vvvi=vc<vvi>;
using vl=vc<ll>;
using vvl=vc<vl>;
using vvvl=vc<vvl>;
template<class T>using smpq=priority_queue<T,vector<T>,greater<T>>;
template<class T>using bipq=priority_queue<T>;
#define rep(i,n) for(ll i=0;i<(ll)(n);i++)
#define REP(i,j,n) for(ll i=(j);i<(ll)(n);i++)
#define DREP(i,n,m) for(ll i=(n);i>=(m);i--)
#define drep(i,n) for(ll i=((n)-1);i>=0;i--)
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(),x.rend()
#define mp make_pair
#define pb push_back
#define eb emplace_back
#define fi first
#define se second
#define is insert
#define bg begin()
#define ed end()
void scan(int&a) { cin >> a; }
void scan(ll&a) { cin >> a; }
void scan(string&a) { cin >> a; }
void scan(char&a) { cin >> a; }
void scan(uint&a) { cin >> a; }
void scan(ull&a) { cin >> a; }
void scan(bool&a) { cin >> a; }
void scan(ld&a){ cin>> a;}
template<class T> void scan(vector<T>&a) { for(auto&x:a) scan(x); }
void read() {}
template<class Head, class... Tail> void read(Head&head, Tail&... tail) { scan(head); read(tail...); }
#define INT(...) int __VA_ARGS__; read(__VA_ARGS__);
#define LL(...) ll __VA_ARGS__; read(__VA_ARGS__);
#define ULL(...) ull __VA_ARGS__; read(__VA_ARGS__);
#define STR(...) string __VA_ARGS__; read(__VA_ARGS__);
#define CHR(...) char __VA_ARGS__; read(__VA_ARGS__);
#define DBL(...) double __VA_ARGS__; read(__VA_ARGS__);
#define LD(...) ld __VA_ARGS__; read(__VA_ARGS__);
#define VC(type, name, ...) vector<type> name(__VA_ARGS__); read(name);
#define VVC(type, name, size, ...) vector<vector<type>> name(size, vector<type>(__VA_ARGS__)); read(name);
void print(int a) { cout << a; }
void print(ll a) { cout << a; }
void print(string a) { cout << a; }
void print(char a) { cout << a; }
void print(uint a) { cout << a; }
void print(bool a) { cout << a; }
void print(ull a) { cout << a; }
void print(double a) { cout << a; }
void print(ld a){ cout<< a; }
template<class T> void print(vector<T>a) { for(int i=0;i<(int)a.size();i++){if(i)cout<<" ";print(a[i]);}cout<<endl;}
void PRT() { cout <<endl; return ; }
template<class T> void PRT(T a) { print(a); cout <<endl; return; }
template<class Head, class... Tail> void PRT(Head head, Tail ... tail) { print(head); cout << " "; PRT(tail...); return; }
template<class T,class F>
bool chmin(T &x, F y){
    if(x>y){
        x=y;
        return true;
    }
    return false;
}
template<class T, class F>
bool chmax(T &x, F y){
    if(x<y){
        x=y;
        return true;
    }
    return false;
}
void YesNo(bool b){
    cout<<(b?"Yes":"No")<<endl;
}
void Yes(){
    cout<<"Yes"<<endl;
}
void No(){
    cout<<"No"<<endl;
}
template<class T>
int popcount(T n){
    return __builtin_popcountll(n);
}
template<class T>
T sum(vc<T>&a){
    return accumulate(all(a),T(0));
}
template<class T>
T max(vc<T>&a){
    return *max_element(all(a));
}
template<class T>
T min(vc<T>&a){
    return *min_element(all(a));
}
template<class T>
void unique(vc<T>&a){
    a.erase(unique(all(a)),a.end());
}
vvi readgraph(int n,int m,int off = -1){
    vvi g(n);
    rep(i, m){
        int u,v;
        cin>>u>>v;
        u+=off,v+=off;
        g[u].push_back(v);
        g[v].push_back(u);
    }
    return g;
}
vvi readtree(int n,int off=-1){
    return readgraph(n,n-1,off);
}
template<class T>
vc<T> presum(vc<T> &a){
    vc<T> ret(a.size()+1);
    rep(i,a.size())ret[i+1]=ret[i]+a[i];
    return ret;
}
template<class T, class F>
vc<T> &operator+=(vc<T> &a,F b){
    for (auto&v:a)v += b;
    return a;
}
template<class T, class F>
vc<T> &operator-=(vc<T>&a,F b){
    for (auto&v:a)v-=b;
    return a;
}
template<class T, class F>
vc<T> &operator*=(vc<T>&a,F b){
    for (auto&v:a)v*=b;
    return a;
}
#endif

/*
https://atcoder.jp/contests/arc039/tasks/arc039_d
https://kntychance.hatenablog.jp/entry/2022/09/16/161858

*/
struct Edge{
    int from;
    int to;
    int id;
};
struct graph{
    vector<vector<Edge>>g;
    vector<int>low,ord;
    vector<int>ea,eb;
    vector<int>used;
    int n;
    graph(int n):n(n),g(n),low(n),ord(n){}
    int edge_num=0;
    void add_edge(int a,int b,int is_both=1){
        g[a].push_back({a,b,edge_num});
        if(is_both)g[b].push_back({b,a,edge_num});
        ea.push_back(a);
        eb.push_back(b);
        used.push_back(0);
        edge_num++;
    }
    struct cycle_scanner{
        vector<int>seen,finish;
        vector<Edge>hist;
        int n;
        vector<vector<Edge>>g;
        cycle_scanner(vector<vector<Edge>>g):g(g),n(g.size()){
        }
        int dfs(int now,const Edge&pre,int can_rev){
            seen[now]=1;    
            hist.push_back(pre);
            for(auto&e:g[now]){
                if(can_rev==0&&pre.id==e.id)continue;
                if(finish[e.to]){
                    continue;
                }
                if(seen[e.to]&&!finish[e.to]){
                    hist.push_back(e);
                    return e.to;
                }
                int res=dfs(e.to,e,can_rev);
                if(res!=-1)return res;
            }
            finish[now]=1;
            hist.pop_back();
            return -1;
        }
        vector<Edge>constructer(int pos){
            vector<Edge>res;
            while(hist.size()){
                auto p=hist.back();hist.pop_back();
                res.push_back(p);
                if(p.from==pos)break;
            }
            reverse(res.begin(), res.end());
            return res;
        }
        //有向グラフなら1,そうでないなら0を与える
        vector<Edge>find_v(int can_rev){
            seen.resize(n),finish.resize(n);
            int pos=-1;
            for(int i=0;i<n;i++){
                if(seen[i])continue;
                pos=dfs(i,{-1,-1,-1},can_rev);
                if(pos!=-1){
                    return constructer(pos);
                }
            }
            return {};
        }
    };
    //有向グラフなら1,そうでないなら0を与える
    vector<Edge> cycle_scan(int can_rev){
        cycle_scanner cyc(g);
        return cyc.find_v(can_rev);
    }
    int lowlinked=0;
    void lowlink(){
        if(lowlinked)return;
        lowlinked=1;
        vector<int>seen(n);
        auto dfs=[&](auto&dfs,int u,int v,int&now)->int{
            seen[u]=1;
            ord[u]=now++;
            low[u]=ord[u];
            for(auto [from,x,i]:g[u]){
                if(i==v)continue;
                if(seen[x]){
                    low[u]=min(low[u],ord[x]);
                }else{
                    used[i]=1;
                    low[u]=min(low[u],dfs(dfs,x,i,now));
                }
            }
            return low[u];
        };
        int now=0;
        for(int i=0;i<n;i++){
            if(!seen[i]){
                dfs(dfs,i,-1,now);
            }
        }
    }
    vector<int>two_comp_num;
    vector<vector<int>>two_comp;
    void make_two_comp(){
        if(two_comp.size())return;
        lowlink();
        two_comp_num=vector<int>(n);
        vector<vector<int>>res;
        dfs1(0,-1,res);
        for(int i=0;i<int(res.size());i++){
            for(auto x:res[i]){
                two_comp_num[x]=i;
            }
        }
        two_comp=res;
    }
    void dfs2(int u,int v,vector<int>&vs);
    int is_bridge(int i){
        if(!used[i])return 0;
        int a1=ea[i],a2=eb[i];
        if(ord[a1]>ord[a2])swap(a1,a2);
        if(ord[a1]>=low[a2])return 0;
        return 1;   
    }
    void dfs1(int u,int v,vector<vector<int>>&res){
        vector<int>vs{u};
        for(auto [_,x,i]:g[u]){
            if(x==v)continue;
            if(!used[i])continue;
            if(!is_bridge(i)){
                dfs2(x,u,res,vs);
            }else{
                dfs1(x,u,res);
            }
        }
        res.push_back(vs);
    }
    void dfs2(int u,int v,vector<vector<int>>&res,vector<int>&vs){
        vs.push_back(u);
        for(auto [_,x,i]:g[u]){
            if(x==v)continue;
            if(!used[i])continue;
            if(!is_bridge(i)){
                dfs2(x,u,res,vs);
            }else{
                dfs1(x,u,res);
            }
        }
    }
    vector<vector<int>>two_g;//二重辺連結成分分解して成分ごとに縮約した気
    void make_two_g(){
        make_two_comp();
        auto res=two_comp;
        two_g.resize(res.size());
        for(int i=0;i<(int)ea.size();i++){
            if(two_comp_num[ea[i]]!=two_comp_num[eb[i]]){
                two_g[two_comp_num[ea[i]]].push_back(two_comp_num[eb[i]]);
                two_g[two_comp_num[eb[i]]].push_back(two_comp_num[ea[i]]);
            } 
        }
    }
    //https://onlinejudge.u-aizu.ac.jp/problems/GRL_3_A
    vector<int>is_art;
    void make_art(){
        lowlink();
        is_art.resize(n);
        int res=0;
        for(auto [_,x,i]:g[0]){
            if(used[i])res++;
        }
        is_art[0]=res>=2;
        for(int i=1;i<n;i++){
            for(auto [_,x,idx]:g[i]){
                if(used[idx]&&ord[i]<=low[x])is_art[i]=1;
            }
        }
    }
    //なんもわかんねーなにこれ
    //https://ei1333.github.io/luzhiled/snippets/graph/bi-connected-components.html
    //https://judge.yosupo.jp/submission/226252
    vector<vector<pair<int,int>>> bc;//おなじ連結成分に属している辺
    vector<vector<int>>bcs;//頂点
    void bic(){
        lowlink();
        vector<int>used(n);
        vector<pair<int,int>>tmp;
        auto dfs=[&](auto&dfs,int u,int v)->void{
            used[u]=1;
            for(auto [_,x,idx]:g[u]){
                if(x==v)continue;
                if(!used[x]||ord[x]<ord[u]){
                    tmp.push_back(minmax(x,u));
                }
                if(!used[x]){
                    dfs(dfs,x,u);
                    if(low[x]>=ord[u]){
                        bc.push_back(vector<pair<int,int>>());
                        while(1){
                            auto p=tmp.back();tmp.pop_back();
                            bc.back().push_back(p);
                            if(p.first==min(x,u)&&p.second==max(x,u)){
                                break;
                            } 
                        }
                    }
                } 
            }
            if(g[u].size()==0){//孤立点
                bcs.push_back(vector<int>{u});
            }
        };
        for(int i=0;i<n;i++){
            if(!used[i])dfs(dfs,i,-1);
        }

        vector<int>added(n);
        for(auto x:bc){
            bcs.push_back(vector<int>());
            for(auto [a,b]:x){
                auto add=[&](int x){
                    if(added[x])return;
                    bcs.back().push_back(x);
                    added[x]=1;
                };
                add(a),add(b);
            }
            for(auto x:bcs.back())added[x]=0;
        } 
    }
};
double pass_time=0;

template<class T,auto op,int extra>
struct base_dsu{
        vector<int>par;
        vector<T>data;
        base_dsu(int n):par(n,-1){
            static_assert(!extra,"e is needed");
        }
        base_dsu(int n,T e):par(n,-1),data(n,e){}
        T& operator[](int i){
            static_assert(extra,"No data");
            return data[leader(i)];
        }
        int root(int x){
            if(par[x]<0)return x;
            else return par[x]=root(par[x]);
        }
        bool same(int x,int y){
            return root(x)==root(y);
        }
        bool merge(int x,int y){
            x=root(x);
            y=root(y);
            if(x==y)return false;
            if(par[x]>par[y])swap(x,y);
            par[x]+=par[y];
            par[y]=x;
            if(extra){
                data[x]=op(data[y],data[x]);
            }
            return true;
        }
        int size(int x){
            return -par[root(x)];
        }
        int leader(int x){
            return root(x);
        }

};
int tf323(int a,int b){return a;}
using dsu=base_dsu<int,tf323,0>;
template<class T,auto op>
using extra_dsu=base_dsu<T,op,1>;
void solve(){
    INT(n,m,q);
    graph g(n);
    vi a(m),b(m);
    rep(i,m){
        cin>>a[i]>>b[i];
        --a[i],--b[i];
        g.add_edge(a[i],b[i],1);
    }
    g.lowlink();
    dsu dsu(n);
    rep(i,m)if(g.is_bridge(i))dsu.merge(a[i],b[i]);
    while(q--){
        INT(x,y);
        --x,--y;
        YesNo(dsu.same(x,y));
    }
    
}
signed main(){
    cin.tie(0)->sync_with_stdio(0);
    pass_time=clock();
    int t=1;
    //cin>>t;
    while(t--)solve();
    pass_time=clock()-pass_time;
    dbg(pass_time/CLOCKS_PER_SEC);
}
0