#1014560 (C++23) No.2301 Namorientation

提出ソース
結果

問題	No.2301 Namorientation
コンテスト
ユーザー	t9unkubj
提出日時	2024-09-30 07:18:15
言語	C++23 (gcc 13.3.0 + boost 1.87.0)
結果	WA
実行時間	-
コード長	12,244 bytes
コンパイル時間	4,923 ms
コンパイル使用メモリ	296,572 KB
実行使用メモリ	68,060 KB
最終ジャッジ日時	2024-09-30 07:18:41
合計ジャッジ時間	20,616 ms
ジャッジサーバーID （参考情報）	judge5 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン	結果
sample	WA * 2
other	WA * 30
権限があれば一括ダウンロードができます
ソースコード

raw source code
#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
double pass_time=0;

/*
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;
        } 
    }
};

void solve(){
    INT(n);
    vector<vector<pair<int,int>>>g(n);
    graph G(n);
    vi a(n),b(n);
    rep(i,n){
        cin>>a[i]>>b[i];
        --a[i],--b[i];
        G.add_edge(a[i],b[i],1);
        g[a[i]].pb({b[i],i});
        g[b[i]].pb({a[i],i});
    }
    vector<string>ans(n);
    auto res=G.cycle_scan(0);
    vi is(n);
    for(auto [to,from,id]:res){
    dbg(to);
        is[to]=1;
        ans[id]="->";
    }   
    auto dfs=[&](auto&dfs,int now,int pre)->void{
        for(auto&[x,i]:g[now]){
            if(x==pre)continue;
            if(is[x])continue;
            if(a[i]==x){
                ans[i]="->";
            }else ans[i]="<-";
            dfs(dfs,x,now);
        }
    };
    rep(i,n){
        if(is[i]){
            dfs(dfs,i,-1);
        }
    }
    rep(i,n)PRT(ans[i]);
}
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);
    
}
yukicoder

結果

ソースコード
