結果

問題 No.1254 補強への架け橋
ユーザー penguinmanpenguinman
提出日時 2020-10-09 22:34:19
言語 C++14
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 314 ms / 2,000 ms
コード長 11,970 bytes
コンパイル時間 2,435 ms
コンパイル使用メモリ 203,996 KB
実行使用メモリ 54,936 KB
最終ジャッジ日時 2023-09-27 18:27:41
合計ジャッジ時間 13,888 ms
ジャッジサーバーID
(参考情報)
judge12 / judge15
このコードへのチャレンジ(β)

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1 ms
4,380 KB
testcase_01 AC 2 ms
4,376 KB
testcase_02 AC 1 ms
4,380 KB
testcase_03 AC 1 ms
4,376 KB
testcase_04 AC 2 ms
4,376 KB
testcase_05 AC 1 ms
4,380 KB
testcase_06 AC 1 ms
4,380 KB
testcase_07 AC 1 ms
4,376 KB
testcase_08 AC 1 ms
4,376 KB
testcase_09 AC 1 ms
4,376 KB
testcase_10 AC 1 ms
4,376 KB
testcase_11 AC 1 ms
4,376 KB
testcase_12 AC 1 ms
4,384 KB
testcase_13 AC 2 ms
4,380 KB
testcase_14 AC 1 ms
4,380 KB
testcase_15 AC 2 ms
4,376 KB
testcase_16 AC 2 ms
4,376 KB
testcase_17 AC 2 ms
4,376 KB
testcase_18 AC 2 ms
4,376 KB
testcase_19 AC 2 ms
4,376 KB
testcase_20 AC 1 ms
4,380 KB
testcase_21 AC 2 ms
4,376 KB
testcase_22 AC 2 ms
4,376 KB
testcase_23 AC 1 ms
4,376 KB
testcase_24 AC 1 ms
4,376 KB
testcase_25 AC 2 ms
4,380 KB
testcase_26 AC 1 ms
4,380 KB
testcase_27 AC 1 ms
4,376 KB
testcase_28 AC 1 ms
4,376 KB
testcase_29 AC 1 ms
4,376 KB
testcase_30 AC 1 ms
4,380 KB
testcase_31 AC 1 ms
4,376 KB
testcase_32 AC 1 ms
4,380 KB
testcase_33 AC 1 ms
4,376 KB
testcase_34 AC 1 ms
4,376 KB
testcase_35 AC 1 ms
4,376 KB
testcase_36 AC 2 ms
4,376 KB
testcase_37 AC 2 ms
4,376 KB
testcase_38 AC 2 ms
4,380 KB
testcase_39 AC 2 ms
4,380 KB
testcase_40 AC 2 ms
4,376 KB
testcase_41 AC 1 ms
4,376 KB
testcase_42 AC 1 ms
4,376 KB
testcase_43 AC 2 ms
4,380 KB
testcase_44 AC 2 ms
4,376 KB
testcase_45 AC 2 ms
4,376 KB
testcase_46 AC 2 ms
4,376 KB
testcase_47 AC 2 ms
4,380 KB
testcase_48 AC 2 ms
4,376 KB
testcase_49 AC 2 ms
4,376 KB
testcase_50 AC 2 ms
4,380 KB
testcase_51 AC 2 ms
4,380 KB
testcase_52 AC 3 ms
4,376 KB
testcase_53 AC 2 ms
4,376 KB
testcase_54 AC 2 ms
4,380 KB
testcase_55 AC 2 ms
4,376 KB
testcase_56 AC 2 ms
4,380 KB
testcase_57 AC 2 ms
4,376 KB
testcase_58 AC 1 ms
4,376 KB
testcase_59 AC 1 ms
4,376 KB
testcase_60 AC 2 ms
4,376 KB
testcase_61 AC 2 ms
4,376 KB
testcase_62 AC 2 ms
4,376 KB
testcase_63 AC 10 ms
7,552 KB
testcase_64 AC 3 ms
4,580 KB
testcase_65 AC 7 ms
5,964 KB
testcase_66 AC 5 ms
5,592 KB
testcase_67 AC 3 ms
4,380 KB
testcase_68 AC 5 ms
5,644 KB
testcase_69 AC 8 ms
6,388 KB
testcase_70 AC 4 ms
5,012 KB
testcase_71 AC 3 ms
4,560 KB
testcase_72 AC 8 ms
6,436 KB
testcase_73 AC 4 ms
4,700 KB
testcase_74 AC 8 ms
6,216 KB
testcase_75 AC 5 ms
5,748 KB
testcase_76 AC 2 ms
4,380 KB
testcase_77 AC 5 ms
5,388 KB
testcase_78 AC 8 ms
7,080 KB
testcase_79 AC 9 ms
7,016 KB
testcase_80 AC 8 ms
6,500 KB
testcase_81 AC 9 ms
7,028 KB
testcase_82 AC 10 ms
6,764 KB
testcase_83 AC 120 ms
44,188 KB
testcase_84 AC 112 ms
43,040 KB
testcase_85 AC 63 ms
28,148 KB
testcase_86 AC 96 ms
37,844 KB
testcase_87 AC 110 ms
40,912 KB
testcase_88 AC 15 ms
9,408 KB
testcase_89 AC 120 ms
43,976 KB
testcase_90 AC 74 ms
29,460 KB
testcase_91 AC 54 ms
24,172 KB
testcase_92 AC 28 ms
14,468 KB
testcase_93 AC 95 ms
36,068 KB
testcase_94 AC 87 ms
32,896 KB
testcase_95 AC 89 ms
32,904 KB
testcase_96 AC 122 ms
41,868 KB
testcase_97 AC 47 ms
20,964 KB
testcase_98 AC 124 ms
42,464 KB
testcase_99 AC 72 ms
27,088 KB
testcase_100 AC 135 ms
45,124 KB
testcase_101 AC 23 ms
13,084 KB
testcase_102 AC 12 ms
8,492 KB
testcase_103 AC 27 ms
14,152 KB
testcase_104 AC 38 ms
18,424 KB
testcase_105 AC 101 ms
35,996 KB
testcase_106 AC 52 ms
22,612 KB
testcase_107 AC 123 ms
43,988 KB
testcase_108 AC 121 ms
43,464 KB
testcase_109 AC 94 ms
35,596 KB
testcase_110 AC 80 ms
32,828 KB
testcase_111 AC 87 ms
34,868 KB
testcase_112 AC 34 ms
17,764 KB
testcase_113 AC 77 ms
31,788 KB
testcase_114 AC 49 ms
22,148 KB
testcase_115 AC 15 ms
9,872 KB
testcase_116 AC 55 ms
25,040 KB
testcase_117 AC 35 ms
17,584 KB
testcase_118 AC 117 ms
41,776 KB
testcase_119 AC 61 ms
26,976 KB
testcase_120 AC 113 ms
40,524 KB
testcase_121 AC 30 ms
15,468 KB
testcase_122 AC 56 ms
24,500 KB
testcase_123 AC 1 ms
4,380 KB
testcase_124 AC 293 ms
54,936 KB
testcase_125 AC 314 ms
54,936 KB
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp: 関数 ‘int main()’ 内:
main.cpp:452:20: 警告: ‘y’ may be used uninitialized [-Wmaybe-uninitialized]
  452 |             while(x!=Z){
      |                   ~^~~
main.cpp:424:10: 備考: ‘y’ はここで定義されています
  424 |     ll x,y;
      |          ^
main.cpp:445:20: 警告: ‘x’ may be used uninitialized [-Wmaybe-uninitialized]
  445 |             while(x!=Z){
      |                   ~^~~
main.cpp:424:8: 備考: ‘x’ はここで定義されています
  424 |     ll x,y;
      |        ^

ソースコード

diff #

#include<bits/stdc++.h>
//using namespace std;
#pragma GCC target("avx")
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#define rep(i,j,n) for(ll i=(ll)(j);i<(ll)(n);i++)
#define REP(i,j,n) for(ll i=(ll)(j);i<=(ll)(n);i++)
#define per(i,j,n) for(ll i=(ll)(j);(ll)(n)<=i;i--)
#define ll long long
#define ALL(a) (a).begin(),(a).end()
#define disup(A,key) distance(A.begin(),upper_bound(ALL(A),(ll)(key)))
#define dislow(A,key) distance(A.begin(),lower_bound(ALL(A),(ll)(key)))
#define pb emplace_back
#define mp std::make_pair
//
#define endl "\n"
//using std::endl;
using std::cin;
using std::cout;
using std::vector;
using std::string;
using std::upper_bound;
using std::lower_bound;
using vi=vector<ll>;
using vii=vector<vi>;
using pii=std::pair<ll,ll>;
//
constexpr ll MOD=1e9+7;
//constexpr ll MOD=998244353;
//constexpr ll MOD=10000000;
//constexpr ll MOD=1e4;
//constexpr ll MOD=1e5;
constexpr ll MAX=3e6;
constexpr ll inf=(1ll<<60);
template<class T>
class prique :public std::priority_queue<T, std::vector<T>, std::greater<T>> {};
template<typename T>
struct Segment_tree{
    ll N;
    T mem;
    vector<T> node;
    Segment_tree(vector<T> &X,T m):mem(m){
        ll sz=X.size();
        N=1;
        while(N<sz) N*=2;
        node.resize(2*N-1,mem);
        rep(i,0,sz) node[N-1+i]=X[i];
        per(i,N-2,0){
            node[i]=Compare(node[i*2+1],node[i*2+2]);
        }
    }
    T Compare(T &A,T &B){
        return A+B;
    }
    void update(ll X,T val){
        X+=N-1;
        node[X]=val;
        while(X>0){
            X=(X-1)/2;
            node[X]=Compare(node[X*2+1],node[X*2+2]);
        }
    }
    T Query(ll a,ll b,ll now=0,ll l=0,ll r=-1){ //[a,b),[l,r)
        if(r<0) r=N;
        if(r<=a||b<=l) return mem;
        if(a<=l&&r<=b) return node[now];
        auto vl=Query(a,b,now*2+1,l,(l+r)/2),vr=Query(a,b,now*2+2,(l+r)/2,r);
        return Compare(vl,vr);
    }
    ll lower_bound(ll left,ll right,T val,ll now=0,ll l=0,ll r=-1){
        if(r<0) r=N;
        if(node[now]<val||l>=right||left>=r) return r;
        else if(now>=N-1) return l;
        ll vl=lower_bound(left,right,val,now*2+1,l,(l+r)/2);
        if(vl==(l+r)/2) return lower_bound(left,right,val,now*2+2,(l+r)/2,r);
        return vl;
    }
};
template<typename T>
struct lazy_Segment_tree{
    int N;
    vector<T> node,lazy;
    T INF;
    vector<bool> flag;
    lazy_Segment_tree(vector<T> X,T Y):INF(Y){
        N=1;
        while(X.size()>N) N*=2;
        node.resize(2*N-1,Y);
        lazy.resize(2*N-1);
        flag.resize(2*N-1);
        rep(i,0,X.size()) node[i+N-1]=X[i];
        per(i,N-2,0) node[i]=compare(node[i*2+1],node[i*2+2]);
    }
    T compare(T X,T Y){
        return std::max(X,Y);
    }
    T plus(T X,int l,int r){
        return X;
    }
    void eval(int now,int l,int r){
        if(flag[now]){
            if(r-l>1){
                flag[now*2+1]=flag[now*2+2]=1;
                lazy[now*2+1]=lazy[now*2+2]=lazy[now];
            }
            node[now]=lazy[now];
            flag[now]=0;
        }
    }
    void update(int a,int b,T add,int now=0,int l=0,int r=-1){
        if(r<0) r=N;
        eval(now,l,r);
        if(b<=l||r<=a) return;
        if(a<=l&&r<=b){
            lazy[now]=add;
            flag[now]=1;
            eval(now,l,r);
        }
        else{
            update(a,b,add,now*2+1,l,(r+l)/2);
            update(a,b,add,now*2+2,(r+l)/2,r);
            node[now]=compare(node[now*2+1],node[now*2+2]);
        }
    }
    T Query(int a,int b,int now=0,int l=0,int r=-1){
        if(r<0) r=N;
        eval(now,l,r);
        if(b<=l||r<=a) return INF;
        if(a<=l&&r<=b) return node[now];
        return compare(Query(a,b,now*2+1,l,(r+l)/2),Query(a,b,now*2+2,(r+l)/2,r));
    }
    ll lower_bound(ll left,ll right,T val,ll now=0,ll l=0,ll r=-1){
        eval(now,l,r);
        if(r<0) r=N;
        if(node[now]<val||l>=right||left>=r) return r;
        else if(now>=N-1) return l;
        ll vl=lower_bound(left,right,val,now*2+1,l,(l+r)/2);
        if(vl==(l+r)/2) return lower_bound(left,right,val,now*2+2,(l+r)/2,r);
        return vl;
    }
};
struct Strongly_Connected_Components{
    ll N,M;
    vii edge,ver;
    vi ind;
    Strongly_Connected_Components(vii e){
        ll n=e.size();
        ll m=0;
        vii revedge(n);
        ind.resize(n);
        rep(i,0,n){
            m+=e[i].size();
            for(auto p:e[i]) revedge[p].pb(i);
        }
        vi num(n,-1),po(n);
        vector<bool> seen(n);
        ll cnt=0;
        rep(i,0,n){
            if(num[i]==-1){
                dfs(i,e,num,cnt);
            }
        }
        rep(i,0,n) po[num[i]]=i;
        per(i,n-1,0){
            ll X=po[i];
            if(!seen[X]){
                std::queue<ll> que;
                vi v;
                que.push(X);
                seen[X]=1;
                while(!que.empty()){
                    ll now=que.front(); que.pop();
                    v.pb(now);
                    ind[now]=ver.size();
                    for(auto p:revedge[now]){
                        if(!seen[p]){
                            seen[p]=1;
                            que.push(p);
                        }
                    }
                }
                ver.pb(v);
            }
        }
        N=ver.size();
        M=0;
        edge.resize(N);
        rep(i,0,n){
            for(auto p:e[i]){
                if(ind[i]==ind[p]) continue;
                M++;
                edge[ind[i]].pb(ind[p]);
            }
        }
    }
    void dfs(ll now,vii &e,vi &num,ll &cnt){
        num[now]=0;
        for(auto next:e[now]){
            if(num[next]==-1){
                dfs(next,e,num,cnt);
            }
        }
        num[now]=cnt++;
    }
};
struct lowlink{
    ll N;
    vii edge;
    vi ord,low,aps;
    vector<bool> used;
    vector<pii> bridges;
    lowlink(vii e):edge(e){
        N=edge.size();
        used.resize(N);
        ord.resize(N);
        low.resize(N);
        ll cnt=0;
        rep(i,0,N){
            if(!used[i]) dfs(i,cnt,-1);
        }
    }
    void dfs(ll now,ll &cnt,ll from){
        used[now]=1;
        ord[now]=cnt++;
        low[now]=ord[now];
        bool flag=0;
        for(auto next:edge[now]){
            if(!used[now]){
                dfs(next,cnt,now);
                low[now]=std::min(low[now],low[next]);
                if(from!=-1&&ord[now]<=low[next]) flag=1;
                if(ord[now]<low[next]) bridges.pb(mp(now,next));
            }
            else if(next!=from) low[now]=std::min(low[now],ord[next]);
        }
        if(from==-1&&edge[now].size()>=2) flag=1;
        if(flag) aps.pb(now);
    }
};
struct Directed_Gragh{
    ll N,M;
    vii edge;
    Directed_Gragh(vii e):edge(e){
        N=edge.size();
        rep(i,0,N) M+=edge[i].size();
    }
    vi sort(){
        vi ret;
        vi cnt(N);
        rep(i,0,N){
            for(auto p:edge[i]) cnt[p]++;
        }
        std::queue<ll> que;
        rep(i,0,N){
            if(cnt[i]==0) que.push(i);
        }
        while(!que.empty()){
            ll now=que.front(); que.pop();
            ret.pb(now);
            for(auto next:edge[now]){
                cnt[next]--;
                if(cnt[next]==0) que.push(next);
            }
        }
        return ret;
    }
};
struct Tree{
    int N;
    vii dp;
    vi par;
    vi dist;
    Tree(vii edge){
        N=edge.size();
        dp.resize(N);
        par.resize(N);
        dist.resize(N,-1);
        for(int i=0;i<N;i++) dp[i].resize(30);
        dist[0]=dp[0][0]=0;
        std::queue<int> que;
        que.push(0);
        while(!que.empty()){
            int now=que.front(); que.pop();
            for(int i=0;i<edge[now].size();i++){
                int next=edge[now][i];
                if(dist[next]==-1){
                    dist[next]=dist[now]+1;
                    que.push(next);
                    par[next]=now;
                    dp[next][0]=now;
                }
            }
        }
        for(int i=1;i<30;i++){
            for(int j=0;j<N;j++) dp[j][i]=dp[dp[j][i-1]][i-1];
        }
    }
    int LCA(int X,int Y){
        if(dist[X]<dist[Y]) std::swap(X,Y);
        {
            int Z=dist[X]-dist[Y];
            for(int i=0;i<30;i++){
                if(Z&(1<<i)){
                    X=dp[X][i];
                }
            }
        }
        if(X==Y) return X;
        for(int i=29;i>=0;i--){
            if(dp[X][i]!=dp[Y][i]){
                X=dp[X][i];
                Y=dp[Y][i];
            }
        }
        return dp[X][0];
    }
};
struct Binary_indexed_tree{
    int N;
    vi bit;
    Binary_indexed_tree(int n):N(n){
        bit.resize(N+1,0);
    }
    void add(int x,ll a){
        for(x;x<=N;x+=(x&-x)) bit[x]+=a;
    }
    ll sum(int x){
        ll ret=0;
        for(x;x>0;x-=(x&-x)) ret+=bit[x];
        return ret;
    }
    ll lower_bound(ll X){
        if(sum(N)<X) return -1;
        ll ret=0,memo=1,sum=0;
        while(memo*2<=N) memo*=2;
        while(memo>0){
            if(memo+ret<=N&&sum+bit[memo+ret]<X){
                sum+=bit[memo+ret];
                ret+=memo;
            }
            memo/=2;
        }
        return ret+1;
    }
};
struct Union_Find{
    ll N;
    vi par;
    vi siz;
    Union_Find(int n):N(n){
        par.resize(N);
        siz.resize(N,1);
        rep(i,0,N) par[i]=i;
    }
    ll root(ll X){
        if(par[X]==X) return X;
        return par[X]=root(par[X]);
    }
    bool same(ll X,ll Y){
        return root(X)==root(Y);
    }
    void unite(ll X,ll Y){
        X=root(X);
        Y=root(Y);
        if(X==Y) return;
        if(siz[Y]<siz[X]) std::swap(X,Y);
        par[X]=Y;
        siz[Y]+=siz[X];
        siz[X]=0;
    }
    ll size(ll X){
        return siz[root(X)];
    }
};
long long modpow(long long a, long long n, long long mod) {
    long long res = 1;
    while (n > 0) {
        if (n & 1) res = res * a % mod;
        a = a * a % mod;
        n >>= 1;
    }
    return res;
}
vi fac,finv,inv;
void COMinit() {
    fac.resize(MAX);
    finv.resize(MAX);
    inv.resize(MAX);
    fac[0] = fac[1] = 1;
    finv[0] = finv[1] = 1;
    inv[1] = 1;
    for (int i = 2; i < MAX; i++){
        fac[i] = fac[i - 1] * i % MOD;
        inv[i] = MOD - inv[MOD%i] * (MOD / i) % MOD;
        finv[i] = finv[i - 1] * inv[i] % MOD;
    }
}
ll COM(ll n,ll r){
    if(n<r||n<0||r<0) return 0;
    return fac[n]*finv[r]%MOD*finv[n-r]%MOD;
}
void comp(vi &A){
    std::map<ll,ll> memo;
    rep(i,0,A.size()) memo[A[i]]=0;
    ll cnt=1;
    for(auto &p:memo) p.second=cnt++;
    rep(i,0,A.size()) A[i]=memo[A[i]];
}
void dec(std::map<ll,ll> &mem,ll X){
    mem[X]--;
    if(mem[X]==0) mem.erase(X);
}
int main(){
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    std::random_device rnd;
    std::mt19937 mt(rnd());
    ll N,M; cin>>N;
    M=N;
    vii edge(N);
    vi X(M),Y(M);
    Union_Find tree(N);
    ll x,y;
    rep(i,0,M){
        cin>>X[i]>>Y[i];
        X[i]--,Y[i]--;
        if(tree.same(X[i],Y[i])){
            x=X[i];
            y=Y[i];
        }
        else{
            tree.unite(X[i],Y[i]);
            edge[X[i]].pb(Y[i]);
            edge[Y[i]].pb(X[i]);
        }
    }
    Tree tr(edge);
    vi ans;
    std::set<pii> set;
    rep(i,0,M){
        if(x==X[i]&&y==Y[i]){
            ans.pb(i+1);
            ll Z=tr.LCA(x,y);
            while(x!=Z){
                ll z=tr.par[x];
                set.insert(mp(z,x));
                set.insert(mp(x,z));
                x=z;
            }
            std::swap(x,y);
            while(x!=Z){
                ll z=tr.par[x];
                set.insert(mp(z,x));
                set.insert(mp(x,z));
                x=z;
            }
            break;
        }
    }
    rep(i,0,M){
        if(set.count(mp(X[i],Y[i]))) ans.pb(i+1);
    }
    cout<<ans.size()<<endl;
    for(auto p:ans) cout<<p<<" ";
    cout<<endl;
}
0