Submission #634633

#	Time	Username	Problem	Language	Result	Execution time	Memory
634633		MohammadAghil	Subtree (INOI20_subtree)	C++17	100 / 100	168 ms	36328 KiB

Main

#include <bits/stdc++.h>
//#pragma GCC optimize("Ofast,unroll-loops")
//#pragma GCC target ("avx2")
using namespace std;

typedef long long ll;
typedef pair<int, int> pp;

#define rep(i,l,r) for(int i = (l); i < (r); i++)
#define per(i,r,l) for(int i = (r); i >= (l); i--)
#define sz(x) (int)x.size()
#define all(x) begin(x), end(x)
#define pb push_back
#define ff first
#define ss second

void dbg(){
    cerr << endl;
}
template<typename Head, typename... Tail> void dbg(Head h, Tail... t){
    cerr << " " << h << ",";
    dbg(t...);
}
#define er(...) cerr << __LINE__ << " <" << #__VA_ARGS__ << ">:", dbg(__VA_ARGS__)

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

void IOS(){
    cin.tie(0) -> sync_with_stdio(0);
//    #ifndef ONLINE_JUDGE
//        freopen("inp.txt", "r", stdin);
//        freopen("out.txt", "w", stdout);
//    #endif
}

const ll mod = 1e9 + 7, maxn = 1e5 + 5, lg = 19, inf = ll(1e9) + 5;

vector<int> adj[maxn], lis[maxn];
vector<pp>  adj2[maxn];
bool vis[maxn], king[maxn];
int cnt_cycle, grp[maxn];

pp dfs(int r, int p){
    pp res = {-1, -1};
    vis[r] = true;
    for(int c: adj[r]) if(c - p){
        if(vis[c]){
            if(res.ff + 1) continue;
            res = {c, cnt_cycle++};
            grp[r] = res.ss;
            lis[grp[r]].pb(r);
        }else{
            pp ret = dfs(c, r);
            if(ret.ff + 1){
                assert(res.ff == -1);
                grp[r] = ret.ss;
                res = ret;
                lis[grp[r]].pb(r);
            }
        }
    }
    if(res.ff == r) res = {-1, -1};
    return res;
}

ll slv(vector<ll> a){
    if(sz(a) < 3) return a[0];
    int n = sz(a);
    vector<ll> suf(n + 1);
    suf[n] = 1;
    per(i,n-1,0){
        suf[i] = suf[i+1]*a[i]%mod;
    }
    ll cr = 0, mul = a[0];
    rep(i,2,n+1) cr += suf[i], cr %= mod;
    ll res = 0;
    rep(i,0,n-1){
        res = (res + cr*mul)%mod;
        cr = (cr - suf[i + 2] + mod)%mod;
        mul = mul*a[i + 1]%mod;
    }
    return res;
}

ll slv2(vector<ll> a){
    ll res = 0;
    ll cr = 0;
    rep(i,0,sz(a)){
        cr = (cr + 1)*a[i]%mod;
        res = (res + cr)%mod;
    }
    return res;
}

ll dp[maxn], dp2[maxn], ans;
void dfs2(int r, int p){
    for(auto[c, u]: adj2[r]){
        if(c - p){
            king[u] = true;
            dfs2(c, r);
        }
    }
    int pos = 0, ptr = 0;
    for(int u: lis[r]){
        dp2[u] = 1;
        for(int c: adj[u]) if(grp[u] - grp[c] && grp[c] - p){
            dp2[u] = dp2[u]*(dp[c] + 1)%mod;
        }
        if(king[u]) pos = ptr;
        ptr++;
    }
    vector<ll> tmp, tmp2;
    rep(i,pos,sz(lis[r])) tmp.pb(dp2[lis[r][i]]);
    rep(i,0,pos) tmp.pb(dp2[lis[r][i]]);
    rep(i,pos+1,sz(lis[r])) dp[lis[r][i]] = dp2[lis[r][i]], tmp2.pb(dp[lis[r][i]]);
    rep(i,0,pos) dp[lis[r][i]] = dp2[lis[r][i]], tmp2.pb(dp[lis[r][i]]);
    dp[lis[r][pos]] = slv(tmp);
    ans = (ans + dp[lis[r][pos]] + slv2(tmp2))%mod;
}

void chk(int r, int p){
    vis[r] = false;
    for(auto[c, y]: adj2[r]) if(c - p){
        assert(vis[c]);
        chk(c, r);
    }
}

int main(){ IOS();
    int n, m; cin >> n >> m;
    rep(i,0,m){
        int u, v; cin >> u >> v; u--, v--;
        adj[u].pb(v), adj[v].pb(u);
    }
    fill(grp, grp + n, -1);
    dfs(0, -1);
    rep(i,0,n){
        if(grp[i] == -1) {
            grp[i] = cnt_cycle++;
            lis[grp[i]].pb(i);
        }
    }
    rep(i,0,n){
        for(int c: adj[i]){
            if(grp[i] - grp[c]){
                adj2[grp[i]].pb({grp[c], c});
            }
        }
    }
    king[0] = true;
    dfs2(grp[0], -1);
    chk(0, -1);
//    rep(i,0,n){
//        er(i+1, dp[i], dp2[i], king[i], grp[i]);
//    }
//    er(slv2({1, 2, 3, 4}));
    cout << ans << '\n';
    return 0;
}

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