Submission #1259118

#	Time	Username	Problem	Language	Result	Execution time	Memory
1259118		mohammadsam	Subtree (INOI20_subtree)	C++20	100 / 100	125 ms	36280 KiB

Main

/*
    in the name of god
*/
//#pragma GCC optimize("Ofast,O3,unroll-loops")
//#pragma GCC target("avx,avx2,fma")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4.1,sse4.2,sse4a,avx,avx2,popcnt,tune=native")

#include <bits/stdc++.h>

using namespace std;
#define int long long 
typedef pair<int,int> pii;
typedef pair<long long ,long long> pll;
typedef long long ll ;

#define File          freopen("input.txt", "r", stdin); freopen("output.txt", "w", stdout);
#define all(V)        V.begin(),V.end()
#define setprec(x)    fixed << setprecision(x)
#define Mp(a,b)       make_pair(a,b)
#define len(V)        (int)(V.size())
#define sep           ' '
#define endl          '\n'
#define pb(x)         push_back(x)
#define fi            first
#define sec           second
#define popcount(x)   __builtin_popcount(x)
#define lid           u<<1
#define rid           (lid)|1
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());

const ll N = 2e5 + 10,SQ=320,LOG=31;
const ll inf = 2e9 , MD = 1e9 + 7;

inline ll md(ll x){ x %= MD; return (x < 0 ? x + MD : x);}
int n , m; 
int par[N];
void DSU(){
    iota(par+1,par+n+1,1);
}
int getpar(int u){
    return (par[u] == u ? u : par[u] = getpar(par[u]));
}
void merge(int u,int v){
    u=getpar(u),v=getpar(v);
    if(u==v) return;
    par[u] = v;
}
pii E[N];
bool mark[N];
int dis[N];
int pr[N];
vector<int> g[N];
vector<int> sub[N];
void dfs(int u,int p){
    mark[u] = 1;
    pr[u] = p;
    dis[u] = dis[p] + 1;
    for(auto h : g[u]){
        if(!mark[h]) dfs(h,u);
        else if(dis[h] < dis[u] and h != p){
            int v = u;
            while(v != h){
                merge(v,pr[v]);
                v = pr[v];
            }
        }
    }
}
int dp[N];
int tmp[N];
int ps[N];
int P[N];
int H[N];
void dfs2(int u,int p){
    P[u] = p;
    int head = -1;
    for(auto h : sub[u]){
        for(auto x  : g[h]){
            if(pr[x] != p and pr[x] != u) dfs2(pr[x],u);
            if(pr[x] == p ) head = h;
        }
    }
    H[u] = head;
    if(len(sub[u]) == 1){
        dp[u] = 1;
        for(auto h : g[sub[u][0]]){
            if(pr[h] != p) dp[u] = md(dp[u] * md(dp[pr[h]] + 1));
        }
        return;
    }
    //cout << u << " -- " << head << endl;
    //for(auto h : sub[u]) cout << h << sep;
    //cout << endl;
    if(head != -1){
        for(auto h : sub[u]){
            tmp[h] = 1;
            for(auto x : g[h]){
                if(pr[x] != p and pr[x] != u) tmp[h] = md(tmp[h] * md(dp[pr[x]]+1));
            }
            //cout << tmp[h] << sep;
        }
        //cout << endl;
        int tot = 1;
        for(auto h : sub[u]) tot = md(tot * tmp[h]);
        int z = 1;
        ps[sub[u][0]] = 0;
        for(auto h : sub[u]){
            z = md(z * tmp[h]);
            ps[sub[u][0]] = md(ps[sub[u][0]] + z);
        }
        ps[sub[u][0]] = md(ps[sub[u][0]] - tot);
        for(int i = len(sub[u]) - 1;i > 0;i--){
            int nxt = (i+1)%len(sub[u]);
            ps[sub[u][i]] = md(tmp[sub[u][i]] * md(1 + ps[sub[u][nxt]]));
            ps[sub[u][i]] = md(ps[sub[u][i]] - tot);
        }
        dp[u] = 0;
        //for(auto h : sub[u]) cout << ps[h] << sep;
        //cout << endl;
        for(auto h : sub[u]) dp[u] = md(dp[u] + ps[h]);
        int ind ;
        for(int i = 0;i < len(sub[u]);i++){
            if(sub[u][i] == head) ind = i;
        }
        ind = (ind + 1)%len(sub[u]);
        vector<int> bad;
        for(int i = ind;;i = (i+1)%len(sub[u])){
            if(sub[u][i] == head) break;
            bad.pb(sub[u][i]);
        }
        int d = 0;
        //cout << "bad" << endl;
        //for(auto h : bad) cout << h << sep;
        //cout << endl;
        for(auto h : bad){
            d = md(tmp[h] * md(d+1));
            dp[u] = md(dp[u] - d);
        }
    }
}
int32_t main() {
    ios_base::sync_with_stdio(false);cout.tie(0);cin.tie(0);
    cin >> n >> m;
    for(int i =1 ;i<=m;i++){
        cin >> E[i].fi >> E[i].sec;
        if(E[i].sec < E[i].fi) swap(E[i].fi,E[i].sec);
        g[E[i].fi].pb(E[i].sec);
        g[E[i].sec].pb(E[i].fi);
    }
    DSU();
    dfs(1,1);
    vector<int> st;
    for(int i = 1;i<=n;i++){
        st.pb(getpar(i));
    }
    sort(all(st));
    st.resize(unique(all(st)) - st.begin());
    for(int i = 1;i<=n;i++){
        int v = lower_bound(all(st),getpar(i)) - st.begin() + 1;
        pr[i] = v;
        sub[v].pb(i);
    }    

    for(int i =1 ;i <= len(st);i++){
        sort(all(sub[i]),[&](int u,int v){return dis[u] < dis[v];});
    }
    dfs2(pr[1],0);
    int ans = 0;
    //for(int i =1 ;i<=len(st);i++) cout << dp[i] << sep;
    //cout << endl;
    for(int u = 1;u<=len(st);u++){
        if(len(sub[u]) == 1) ans = md(ans + dp[u]);
        else{
            for(auto h : sub[u]){
                tmp[h] = 1;
                for(auto x : g[h]){
                    if(pr[x] != P[u] and pr[x] != u) tmp[h] = md(tmp[h] * md(dp[pr[x]]+1));
                }
            }
            //cout << u << " | ";
            //for(auto h : sub[u]) cout << tmp[h] << sep;
            //cout << endl;
            int tot = 1;
            for(auto h : sub[u]) tot = md(tot * tmp[h]);
            int z = 1;
            //cout << tot << endl;
            ps[sub[u][0]] = 0;
            for(auto h : sub[u]){
                z = md(z * tmp[h]);
                ps[sub[u][0]] = md(ps[sub[u][0]] + z);
            }
            //cout << ps[sub[u][0]] << endl;
            ps[sub[u][0]] = md(ps[sub[u][0]] - tot);
            for(int i = len(sub[u]) - 1;i > 0;i--){
                int nxt = (i+1)%len(sub[u]);
                ps[sub[u][i]] = md(tmp[sub[u][i]] * md(1 + ps[sub[u][nxt]]));
                ps[sub[u][i]] = md(ps[sub[u][i]] - tot);
                //cout << ps[sub[u][i]] << sep;
            }
            //cout << endl;
            for(auto h : sub[u]) ans = md(ans + ps[h]);
        }
    }
    cout << ans << endl;
    return 0;
}

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