Submission #634577

#TimeUsernameProblemLanguageResultExecution timeMemory
634577MohammadAghilSubtree (INOI20_subtree)C++17
12 / 100
135 ms36264 KiB
#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], adj2[maxn], lis[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; }else{ pp ret = dfs(c, r); if(ret.ff + 1){ grp[r] = ret.ss; res = ret; king[r] = ret.ff == 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(int c: adj2[r]){ if(c - p){ 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; } 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]); } } } dfs2(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; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...