Submission #469049

#	Time	Username	Problem	Language	Result	Execution time	Memory
469049		alirezasamimi100	Subtree (INOI20_subtree)	C++17	100 / 100	131 ms	29296 KiB

Main

#include <bits/stdc++.h>
#pragma GCC optimize("Ofast,unroll-loops")
/*#pragma comment(linker, "/stack:200000000")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,fma,tune=native")*/
/*#pragma GCC optimize("O2")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("avx,avx2,sse,sse2,fma")*/
using namespace std;
using ll=long long int;
using ld=long double;
using pll=pair<ll,ll>;
using pii=pair<int,int>;
#define F first
#define S second
#define pb push_back
#define mp make_pair
#define lc v<<1
#define rc v<<1|1
#define fast_io ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);
const int N=2e5+10,LN=18,M=5e5+10,SQ=350,B=737,inf=1e9+10;
const ll INF=1e18;
const ld ep=1e-7;
const int MH=1000696969,MD=998244353,MOD=1000000007;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
#define ordered_set tree<pll, null_type,less<pll>, rb_tree_tag,tree_order_statistics_node_update>
ll pow(ll x, ll y, ll mod){
    ll ans=1;
    while (y != 0) {
        if (y & 1) ans = ans * x % mod;
        y >>= 1;
        x = x * x % mod;
    }
    return ans;
}
ll n,m,ans,fl[N],P[N],dp[N],pd[N],dd[N];
vector<ll> adj[N],c[N];
void dfs(ll v, ll p){
    fl[v]=v;
    P[v]=p;
    for(ll u : adj[v]){
        if(u==p || fl[u]==fl[v]) continue;
        if(!fl[u]) dfs(u,v);
        else{
            ll x=v;
            while(x!=u){
                fl[x]=u;
                c[u].pb(x);
                x=P[x];
            }
        }
    }
}
void sfd(ll v, ll p){
    for(ll t : c[v]){
        pd[t]=1;
        for(ll u : adj[t]){
            u=fl[u];
            if(u!=p && u!=v){
                sfd(u,v);
                pd[t]=pd[t]*(dp[u]+1)%MOD;
            }
        }
    }
    if(c[v].size()==1){
        dp[v]=pd[v];
        ans=(ans+dp[v])%MOD;
        return;
    }
    dd[c[v].size()]=1;
    dd[c[v].size()+1]=0;
    ll t=0;
    for(ll i=c[v].size()-1; i; i--){
        dd[i]=dd[i+1]*pd[c[v][i]]%MOD;
        t=(t+1)*pd[c[v][i]]%MOD;
        ans=(ans+t)%MOD;
    }
    for(ll i=c[v].size()-1; i; i--){
        dd[i]=(dd[i]+dd[i+1])%MOD;
    }
    t=1;
    for(ll i=0; i<c[v].size(); i++){
        t=t*pd[c[v][i]]%MOD;
        dp[v]=(dp[v]+t*dd[i+2])%MOD;
    }
    ans=(ans+dp[v])%MOD;
}
int main(){
    fast_io;
    cin >> n >> m;
    for(ll i=0; i<m; i++){
        ll v,u;
        cin >> v >> u;
        adj[v].pb(u);
        adj[u].pb(v);
    }
    dfs(1,0);
    for(ll i=1; i<=n; i++){
        if(fl[i]==i){
            c[i].pb(i);
            reverse(c[i].begin(),c[i].end());
        }
    }
    sfd(1,0);
    cout << ans << '\n';
    return 0;
}

Compilation message (stderr)

Main.cpp: In function 'void sfd(ll, ll)':
Main.cpp:84:18: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   84 |     for(ll i=0; i<c[v].size(); i++){
      |                 ~^~~~~~~~~~~~

• Subtask 1: 8 / 8
• Subtask 2: 12 / 12
• Subtask 3: 30 / 30
• Subtask 4: 50 / 50