oj.uz

Submission #634611

# Submission time Handle Problem Language Result Execution time Memory
634611 2022-08-24T15:45:20 Z MohammadAghil Subtree (INOI20_subtree) C++17
12 / 100
 157 ms 36360 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], 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;
        }else{
            pp ret = dfs(c, r);
            if(ret.ff + 1){
                assert(res.ff == -1);
                grp[r] = ret.ss;
                res = ret;
            }
        }
    }
    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(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
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 4 ms 7380 KB Output is correct
8 Correct 4 ms 7380 KB Output is correct
9 Incorrect 4 ms 7392 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 12 ms 8620 KB Output is correct
3 Correct 132 ms 19588 KB Output is correct
4 Correct 106 ms 19512 KB Output is correct
5 Correct 118 ms 19700 KB Output is correct
6 Correct 123 ms 19624 KB Output is correct
7 Correct 128 ms 32580 KB Output is correct
8 Correct 130 ms 27796 KB Output is correct
9 Correct 136 ms 28232 KB Output is correct
10 Correct 93 ms 20588 KB Output is correct
11 Correct 108 ms 19648 KB Output is correct
12 Correct 133 ms 19020 KB Output is correct
13 Correct 122 ms 18984 KB Output is correct
14 Correct 102 ms 25284 KB Output is correct
15 Correct 130 ms 34628 KB Output is correct
16 Correct 148 ms 36360 KB Output is correct
17 Correct 157 ms 18944 KB Output is correct
18 Correct 127 ms 19100 KB Output is correct
19 Correct 122 ms 19060 KB Output is correct
20 Correct 90 ms 20036 KB Output is correct
21 Correct 106 ms 20352 KB Output is correct
22 Correct 88 ms 20036 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 4 ms 7380 KB Output is correct
8 Correct 4 ms 7380 KB Output is correct
9 Incorrect 4 ms 7392 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 4 ms 7380 KB Output is correct
8 Correct 4 ms 7380 KB Output is correct
9 Incorrect 4 ms 7392 KB Output isn't correct
10 Halted 0 ms 0 KB -