oj.uz

Submission #634596

# Submission time Handle Problem Language Result Execution time Memory
634596 2022-08-24T15:29:56 Z MohammadAghil Subtree (INOI20_subtree) C++17
12 / 100
 156 ms 36324 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){
                assert(res.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 4 ms 7380 KB Output is correct
4 Correct 4 ms 7380 KB Output is correct
5 Correct 4 ms 7380 KB Output is correct
6 Correct 4 ms 7380 KB Output is correct
7 Correct 5 ms 7288 KB Output is correct
8 Correct 4 ms 7380 KB Output is correct
9 Incorrect 4 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 9 ms 7320 KB Output is correct
2 Correct 10 ms 8532 KB Output is correct
3 Correct 118 ms 19024 KB Output is correct
4 Correct 135 ms 19020 KB Output is correct
5 Correct 120 ms 19028 KB Output is correct
6 Correct 142 ms 18952 KB Output is correct
7 Correct 136 ms 32312 KB Output is correct
8 Correct 119 ms 27284 KB Output is correct
9 Correct 134 ms 27368 KB Output is correct
10 Correct 128 ms 20048 KB Output is correct
11 Correct 100 ms 19372 KB Output is correct
12 Correct 156 ms 18888 KB Output is correct
13 Correct 120 ms 18888 KB Output is correct
14 Correct 116 ms 24900 KB Output is correct
15 Correct 142 ms 34376 KB Output is correct
16 Correct 123 ms 36324 KB Output is correct
17 Correct 125 ms 18804 KB Output is correct
18 Correct 122 ms 18964 KB Output is correct
19 Correct 128 ms 18952 KB Output is correct
20 Correct 85 ms 19532 KB Output is correct
21 Correct 107 ms 19756 KB Output is correct
22 Correct 92 ms 19636 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 4 ms 7380 KB Output is correct
4 Correct 4 ms 7380 KB Output is correct
5 Correct 4 ms 7380 KB Output is correct
6 Correct 4 ms 7380 KB Output is correct
7 Correct 5 ms 7288 KB Output is correct
8 Correct 4 ms 7380 KB Output is correct
9 Incorrect 4 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 4 ms 7380 KB Output is correct
4 Correct 4 ms 7380 KB Output is correct
5 Correct 4 ms 7380 KB Output is correct
6 Correct 4 ms 7380 KB Output is correct
7 Correct 5 ms 7288 KB Output is correct
8 Correct 4 ms 7380 KB Output is correct
9 Incorrect 4 ms 7380 KB Output isn't correct
10 Halted 0 ms 0 KB -