oj.uz

Submission #634577

# Submission time Handle Problem Language Result Execution time Memory
634577 2022-08-24T15:12:19 Z MohammadAghil Subtree (INOI20_subtree) C++17
12 / 100
 135 ms 36264 KB 
#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;
}

Subtask #1
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 7380 KB Output is correct
2 Correct 4 ms 7380 KB Output is correct
3 Correct 5 ms 7380 KB Output is correct
4 Correct 4 ms 7392 KB Output is correct
5 Correct 4 ms 7380 KB Output is correct
6 Correct 4 ms 7380 KB Output is correct
7 Correct 4 ms 7380 KB Output is correct
8 Correct 4 ms 7344 KB Output is correct
9 Incorrect 3 ms 7380 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 7380 KB Output is correct
2 Correct 9 ms 8532 KB Output is correct
3 Correct 111 ms 19028 KB Output is correct
4 Correct 107 ms 18908 KB Output is correct
5 Correct 112 ms 19020 KB Output is correct
6 Correct 105 ms 19024 KB Output is correct
7 Correct 125 ms 32376 KB Output is correct
8 Correct 135 ms 27436 KB Output is correct
9 Correct 126 ms 27340 KB Output is correct
10 Correct 99 ms 19932 KB Output is correct
11 Correct 96 ms 19260 KB Output is correct
12 Correct 120 ms 18888 KB Output is correct
13 Correct 120 ms 18892 KB Output is correct
14 Correct 106 ms 24932 KB Output is correct
15 Correct 128 ms 34456 KB Output is correct
16 Correct 129 ms 36264 KB Output is correct
17 Correct 129 ms 18920 KB Output is correct
18 Correct 116 ms 18892 KB Output is correct
19 Correct 116 ms 18964 KB Output is correct
20 Correct 105 ms 19592 KB Output is correct
21 Correct 95 ms 19748 KB Output is correct
22 Correct 89 ms 19644 KB Output is correct

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 7380 KB Output is correct
2 Correct 4 ms 7380 KB Output is correct
3 Correct 5 ms 7380 KB Output is correct
4 Correct 4 ms 7392 KB Output is correct
5 Correct 4 ms 7380 KB Output is correct
6 Correct 4 ms 7380 KB Output is correct
7 Correct 4 ms 7380 KB Output is correct
8 Correct 4 ms 7344 KB Output is correct
9 Incorrect 3 ms 7380 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #4
0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 7380 KB Output is correct
2 Correct 4 ms 7380 KB Output is correct
3 Correct 5 ms 7380 KB Output is correct
4 Correct 4 ms 7392 KB Output is correct
5 Correct 4 ms 7380 KB Output is correct
6 Correct 4 ms 7380 KB Output is correct
7 Correct 4 ms 7380 KB Output is correct
8 Correct 4 ms 7344 KB Output is correct
9 Incorrect 3 ms 7380 KB Output isn't correct
10 Halted 0 ms 0 KB -