oj.uz

Submission #593080

# Submission time Handle Problem Language Result Execution time Memory
593080 2022-07-10T11:03:45 Z radal Subtree (INOI20_subtree) C++17
12 / 100
 76 ms 18236 KB 
#include <bits/stdc++.h>
//#pragma GCC target("sse,sse2")
//#pragma GCC optimize("unroll-loops,O3")
#define rep(i,l,r) for (int i = l; i < r; i++)
#define repr(i,r,l) for (int i = r; i >= l; i--)
#define X first
#define Y second
#define all(x) (x).begin() , (x).end()
#define pb push_back
#define endl '\n'
#define debug(x) cerr << #x << " : " << x << endl;
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int,int> pll;
constexpr int N = 1e5+5,mod = 1e9+7,inf = 1e9+10;
inline int mkay(int a,int b){
    if (a+b >= mod) return a+b-mod;
    if (a+b < 0) return a+b+mod;
    return a+b;
}
 
inline int poww(int a,int k){
    if (k < 0) return 0;
    int z = 1;
    while (k){
        if (k&1) z = 1ll*z*a%mod;
        a = 1ll*a*a%mod;
        k >>= 1;
    } 
    return z; 
}
int n,m,h[N],lw[N],dp[N][2][2][2]; // root bega
bool vis[N];
int mark[N];
vector<int> adj[N];
void pre(int v,int p){
    lw[v] = inf;
    vis[v] = 1;
    for (int u : adj[v]){
        if (u == p) continue;
        if (vis[u] && h[u] < h[v]){
            mark[v] = v;
            lw[v] = h[u];
            continue;
        }
        if (vis[u]) continue;
        h[u] = h[v]+1;
        pre(u,v);
        if (lw[u] <= h[v]){
            mark[v] = u;
            lw[v] = lw[u];
        }
    }
}
void dfs(int v){
    vis[v] = 1;
    for (int u : adj[v]) if (!vis[u])
        dfs(u);
    if (lw[v] > n){
        dp[v][1][0][0] = 1;
        dp[v][0][0][0] = 1;
        int t = 0;
        for (int u : adj[v]){
            if (h[u] == h[v]+1){
                t++;
                dp[v][0][0][0] = mkay(dp[v][0][0][0],mkay(dp[u][0][0][0],dp[u][0][0][1]));
                dp[v][1][0][0] = 1ll*dp[v][1][0][0]*mkay(dp[u][1][0][0],dp[u][1][0][1])%mod;
            }
        }
        dp[v][0][0][0] = mkay(dp[v][0][0][0],dp[v][1][0][0]);
        dp[v][1][0][0] = mkay(dp[v][1][0][0],1);
        dp[v][0][0][0] -= t;
        if (dp[v][0][0][0] < 0) dp[v][0][0][0] += mod;
        return;
    }
    if (mark[v] == v){
        int t = 0;
        dp[v][0][0][1] = 1;
        dp[v][1][1][0] = 1;
        dp[v][1][0][1] = 1;
        dp[v][1][1][1] = 1;
        for(int u : adj[v]){
            if (h[u] == h[v]+1){
                t++;
                dp[v][0][0][1] = mkay(dp[v][0][0][1],mkay(dp[u][0][0][0],dp[u][0][0][1]));
                dp[v][1][1][0] = 1ll*dp[v][1][1][0]*mkay(dp[u][1][0][0],dp[u][1][0][1])%mod;
            }
        }
        dp[v][0][1][0] = dp[v][1][1][0];
        dp[v][0][0][1] = mkay(dp[v][0][0][1],-t);
        dp[v][0][1][1] = dp[v][0][0][1];
        return;
    }
    if(lw[v] < h[v]){
        int t = 0;
        dp[v][1][0][1] = 1;
        dp[v][1][1][1] = 1;
        dp[v][1][0][0] = 1;
        dp[v][1][1][0] = 1;
        for (int u : adj[v]){
            if (h[u] == h[v]+1){
                t++;
                if (u == mark[v]){
                    dp[v][0][0][1] = mkay(dp[v][0][0][1],dp[u][0][1][1]);
                    dp[v][1][0][1] = 1ll*dp[v][1][0][1]*dp[u][1][0][1]%mod;
                    dp[v][0][1][1] = mkay(dp[v][0][1][1],dp[u][0][1][1]);
                    dp[v][1][1][1] = 1ll*dp[v][1][1][1]*dp[u][1][1][1]%mod;
                    dp[v][0][0][0] = mkay(dp[v][0][0][0],dp[u][0][1][0]);
                    dp[v][0][1][0] = mkay(dp[v][0][1][0],dp[u][0][1][0]);
                    dp[v][1][1][0] = 1ll*dp[v][1][1][0]*dp[u][1][1][0]%mod;
                    dp[v][1][0][0] = 1ll*dp[v][1][0][0]*dp[u][0][0][0]%mod;
                }
                else{
                    dp[v][0][0][1] = mkay(dp[v][0][0][1],mkay(dp[u][0][0][0],dp[u][0][0][1]));
                    dp[v][1][0][1] = 1ll*dp[v][1][0][1]*mkay(dp[u][1][0][1],dp[u][1][0][0])%mod;
                    dp[v][0][1][1] = mkay(dp[v][0][1][1],mkay(dp[u][0][0][1],dp[u][0][0][0]));
                    dp[v][1][1][1] = 1ll*dp[v][1][1][1]*mkay(dp[u][1][1][0],dp[u][1][1][1])%mod;
                    dp[v][1][1][0] = 1ll*dp[v][1][1][0]*mkay(dp[u][1][0][1],dp[u][1][0][0])%mod;
                    dp[v][1][0][0] = 1ll*dp[v][1][0][0]*mkay(dp[u][1][0][0],dp[u][1][0][1])%mod;
                }
            }
        }
        dp[v][0][0][1] = mkay(dp[v][0][0][1],-(t-1)+dp[v][1][0][1]);
        dp[v][0][1][1] = mkay(dp[v][0][1][1],-(t-1)+dp[v][1][1][1]);
        dp[v][0][0][0] = mkay(dp[v][0][0][0],dp[v][1][0][0]);
        dp[v][0][1][0] = mkay(dp[v][0][1][0],dp[v][1][1][0]);
        dp[v][1][1][1] = mkay(dp[v][1][1][1],1);
        dp[v][1][0][1] = mkay(1,dp[v][1][0][1]);
        return;
    }
    dp[v][1][0][0] = 1;
    dp[v][1][0][1] = 1;
    int t = 0;
    for (int u : adj[v]){
        if (h[u] == h[v]+1){
            t++;
            if (u == mark[v]){
                dp[v][1][0][0] = 1ll*dp[v][1][0][0]*dp[u][0][0][0]%mod;
                dp[v][1][0][1] = 1ll*dp[v][1][0][1]*dp[u][1][0][1]%mod;
                dp[v][0][0][1] = mkay(dp[v][0][0][1],mkay(dp[u][0][1][1],dp[u][0][1][0]));
            }
            else{
                dp[v][1][0][0] = 1ll*dp[v][1][0][0]*mkay(dp[u][1][0][1],dp[u][1][0][0])%mod;
                dp[v][1][0][1] = 1ll*dp[v][1][0][1]*mkay(dp[u][1][0][1],dp[u][1][0][0])%mod;
                dp[v][0][0][1] = mkay(dp[v][0][0][1],mkay(dp[u][0][0][1],dp[u][0][0][0]));
            }
        }
    }
    dp[v][1][0][1] = mkay(dp[v][1][0][1],1);
    dp[v][0][0][1] = mkay(dp[v][0][0][1],dp[v][1][0][1]-t);
    dp[v][0][0][0] = dp[v][1][0][0];
}
int main(){
    ios :: sync_with_stdio(0); cin.tie(0);
    cin >> n >> m;
    rep(i,0,m){
        int u,v;
        cin >> u >> v;
        adj[u].pb(v);
        adj[v].pb(u);
    }
    pre(1,0);
    memset(vis,0,sizeof vis);
    dfs(1);
    dp[1][0][0][0] = mkay(dp[1][0][0][0],dp[1][0][0][1]-1);
    cout << dp[1][0][0][0];
    return 0;
}

Subtask #1
0 / 8.0

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

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2676 KB Output is correct
2 Correct 5 ms 3540 KB Output is correct
3 Correct 49 ms 11016 KB Output is correct
4 Correct 51 ms 11068 KB Output is correct
5 Correct 47 ms 11020 KB Output is correct
6 Correct 59 ms 11064 KB Output is correct
7 Correct 65 ms 16524 KB Output is correct
8 Correct 66 ms 14516 KB Output is correct
9 Correct 60 ms 14556 KB Output is correct
10 Correct 40 ms 11540 KB Output is correct
11 Correct 42 ms 11180 KB Output is correct
12 Correct 55 ms 10984 KB Output is correct
13 Correct 55 ms 10892 KB Output is correct
14 Correct 43 ms 13476 KB Output is correct
15 Correct 76 ms 17636 KB Output is correct
16 Correct 65 ms 18236 KB Output is correct
17 Correct 58 ms 10908 KB Output is correct
18 Correct 57 ms 11020 KB Output is correct
19 Correct 54 ms 11016 KB Output is correct
20 Correct 38 ms 11300 KB Output is correct
21 Correct 37 ms 11416 KB Output is correct
22 Correct 37 ms 11316 KB Output is correct

Subtask #3
0 / 30.0

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

Subtask #4
0 / 50.0

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