oj.uz

Submission #593008

# Submission time Handle Problem Language Result Execution time Memory
593008 2022-07-10T07:19:20 Z radal Subtree (INOI20_subtree) C++17
12 / 100
 69 ms 16688 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]; // root bega
bool vis[N],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] = 1;
            lw[v] = h[u];
            continue;
        }
        h[u] = h[v]+1;
        pre(u,v);
        if (lw[u] <= h[v])
            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] = 1;
        dp[v][0][0] = 1;
        int t = 0;
        for (int u : adj[v]){
            if (h[u] == h[v]+1){
                t++;
                dp[v][0][0] = mkay(dp[v][0][0],dp[u][0][0]);
                dp[v][1][0] = 1ll*dp[v][1][0]*dp[u][1][0]%mod;
            }
        }
        dp[v][0][0] = mkay(dp[v][0][0],dp[v][1][0]);
        dp[v][1][0] = mkay(dp[v][1][0],1);
        dp[v][0][0] -= t;
        if (dp[v][0][0] < 0) dp[v][0][0] += mod;
        return;
    }
}
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]--;
    if (dp[1][0][0] < 0) dp[1][0][0] += mod;
    cout << dp[1][0][0];
    return 0;
}

Subtask #1
0 / 8.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 2908 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2680 KB Output is correct
2 Correct 5 ms 3332 KB Output is correct
3 Correct 50 ms 9484 KB Output is correct
4 Correct 55 ms 9388 KB Output is correct
5 Correct 48 ms 9392 KB Output is correct
6 Correct 58 ms 9500 KB Output is correct
7 Correct 61 ms 15008 KB Output is correct
8 Correct 69 ms 13020 KB Output is correct
9 Correct 57 ms 13004 KB Output is correct
10 Correct 39 ms 9932 KB Output is correct
11 Correct 38 ms 9668 KB Output is correct
12 Correct 53 ms 9340 KB Output is correct
13 Correct 53 ms 9408 KB Output is correct
14 Correct 40 ms 11972 KB Output is correct
15 Correct 61 ms 15872 KB Output is correct
16 Correct 68 ms 16688 KB Output is correct
17 Correct 52 ms 9364 KB Output is correct
18 Correct 55 ms 9344 KB Output is correct
19 Correct 52 ms 9404 KB Output is correct
20 Correct 34 ms 9660 KB Output is correct
21 Correct 35 ms 9824 KB Output is correct
22 Correct 36 ms 9820 KB Output is correct

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 2908 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 50.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 2908 KB Output isn't correct
2 Halted 0 ms 0 KB -