結果

問題 No.1451 集団登校
ユーザー kotatsugame
提出日時 2021-03-31 15:34:53
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 166 ms / 2,000 ms
コード長 3,209 bytes
コンパイル時間 934 ms
コンパイル使用メモリ 76,140 KB
実行使用メモリ 6,820 KB
最終ジャッジ日時 2024-12-15 00:29:21
合計ジャッジ時間 4,416 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 27
権限があれば一括ダウンロードができます
コンパイルメッセージ
a.cpp:9:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]

ソースコード

diff #
プレゼンテーションモードにする

#line 1 "a.cpp"
#include<iostream>
#include<vector>
using namespace std;
#line 2 "/home/kotatsugame/library/datastructure/UF.cpp"
struct UF{
    int n;
    vector<int>parent,rank;
    UF(int n_=0):n(n_),parent(n_),rank(n_,1)
    {
        for(int i=0;i<n_;i++)parent[i]=i;
    }
    int find(int a){return parent[a]!=a?parent[a]=find(parent[a]):a;}
    bool same(int a,int b){return find(a)==find(b);}
    bool unite(int a,int b)
    {
        a=find(a),b=find(b);
        if(a==b)return false;
        if(rank[a]<rank[b])
        {
            parent[a]=b;
            rank[b]+=rank[a];
        }
        else
        {
            parent[b]=a;
            rank[a]+=rank[b];
        }
        return true;
    }
    int size(int a){return rank[find(a)];}
};
#line 3 "/home/kotatsugame/library/math/modint.cpp"
#include<utility>
template<int m>
struct modint{
    unsigned int x;
    constexpr modint()noexcept:x(){}
    template<typename T>
    constexpr modint(T x_)noexcept:x((x_%=m)<0?x_+m:x_){}
    constexpr unsigned int val()const noexcept{return x;}
    constexpr modint&operator++()noexcept{if(++x==m)x=0;return*this;}
    constexpr modint&operator--()noexcept{if(x==0)x=m;--x;return*this;}
    constexpr modint operator++(int)noexcept{modint res=*this;++*this;return res;}
    constexpr modint operator--(int)noexcept{modint res=*this;--*this;return res;}
    constexpr modint&operator+=(const modint&a)noexcept{x+=a.x;if(x>=m)x-=m;return*this;}
    constexpr modint&operator-=(const modint&a)noexcept{if(x<a.x)x+=m;x-=a.x;return*this;}
    constexpr modint&operator*=(const modint&a)noexcept{x=(unsigned long long)x*a.x%m;return*this;}
    constexpr modint&operator/=(const modint&a)noexcept{return*this*=a.inv();}
    constexpr modint operator+()const noexcept{return*this;}
    constexpr modint operator-()const noexcept{return modint()-*this;}
    constexpr modint pow(long long n)const noexcept
    {
        if(n<0)return pow(-n).inv();
        modint x=*this,r=1;
        for(;n;x*=x,n>>=1)if(n&1)r*=x;
        return r;
    }
    constexpr modint inv()const noexcept
    {
        int s=x,t=m,x=1,u=0;
        while(t)
        {
            int k=s/t;
            s-=k*t;
            swap(s,t);
            x-=k*u;
            swap(x,u);
        }
        return modint(x);
    }
    friend constexpr modint operator+(const modint&a,const modint&b){return modint(a)+=b;}
    friend constexpr modint operator-(const modint&a,const modint&b){return modint(a)-=b;}
    friend constexpr modint operator*(const modint&a,const modint&b){return modint(a)*=b;}
    friend constexpr modint operator/(const modint&a,const modint&b){return modint(a)/=b;}
    friend constexpr bool operator==(const modint&a,const modint&b){return a.x==b.x;}
    friend constexpr bool operator!=(const modint&a,const modint&b){return a.x!=b.x;}
    friend ostream&operator<<(ostream&os,const modint&a){return os<<a.x;}
    friend istream&operator>>(istream&is,modint&a){long long v;is>>v;a=modint(v);return is;}
};
#line 6 "a.cpp"
using mint=modint<(int)1e9+7>;
int N,M;
mint ans[1<<17];
main()
{
    cin>>N>>M;
    vector<pair<int,int> >E;
    UF uf(N);
    for(int i=0;i<M;i++)
    {
        int a,b;cin>>a>>b;
        a--,b--;
        a=uf.find(a);
        b=uf.find(b);
        int asz=uf.size(a),bsz=uf.size(b);
        if(uf.unite(a,b)&&asz==bsz)E.push_back(make_pair(a,b));
    }
    for(int i=0;i<N;i++)if(uf.find(i)==i)ans[i]=1;
    for(int i=E.size();i--;)
    {
        int a=E[i].first,b=E[i].second;
        mint T=ans[a]+ans[b];
        ans[a]=ans[b]=T/2;
    }
    for(int i=0;i<N;i++)cout<<ans[i]<<endl;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0