oj.uz

Submission #418452

# Submission time Handle Problem Language Result Execution time Memory
418452 2021-06-05T11:30:24 Z parsabahrami Subtree (INOI20_subtree) C++17
12 / 100
 256 ms 30916 KB 
// Call my Name and Save me from The Dark
#include <bits/stdc++.h>
 
using namespace std;

typedef long long int ll;
typedef pair<int, int> pii;
 
#define SZ(x)                       (int) x.size()
#define F                           first
#define S                           second

const int N = 1e5 + 10, MOD = 1e9 + 7;
int dp[N], M[N], dp2[N], up[N], low[N], H[N], rt[N], B[N], fr[N], to[N], n, m; vector<int> vec[N], adj[N];
int pd[N];

void preDFS(int v, int p = -1) {
    low[v] = H[v]; M[v] = 1;
    for (int id : adj[v]) {
        int u = fr[id] ^ to[id] ^ v;
        if (!M[u]) {
            H[u] = H[v] + 1; preDFS(u, v);
            if (low[u] > H[v]) B[id] = 1;
            low[v] = min(low[v], low[u]);
        } else if (u != p) 
            low[v] = min(low[v], H[u]);
    }
}

int Find(int v) { return !rt[v] ? v : rt[v] = Find(rt[v]); }

void Union(int u, int v) {
    u = Find(u), v = Find(v);
    if (u == v) return;
    if (SZ(vec[u]) < SZ(vec[v])) 
        swap(u, v);
    for (int w : vec[u]) 
        vec[v].push_back(w);
    rt[u] = v;
}

void DFS(int v, int p = -1) {
    vector<int> tmp;
    for (int &u : vec[v]) 
        for (int &w : adj[u])  
            if (w != p) 
                tmp.push_back(w);
            else up[v] = u;
    for (int &u : tmp) 
        DFS(u, v);
}

int calc_dp2(vector<int> &A) {
    int ret = 0, S = 0;
    for (int i = 0; i < SZ(A); i++) {
        S = A[i] * 1ll * (S + 1) % MOD;
        ret = (ret + S) % MOD;
    }
    return ret;
}

int calc_dp1(vector<int> &A) {
    int ret = calc_dp2(A), S = 1;
    fill(pd, pd + SZ(A) + 1, 0);
    for (int i = 0; i < SZ(A); i++) {
        S = 1ll * S * A[i] % MOD;
        pd[i] = S;
        if (i > 0) pd[i] = (pd[i] + pd[i - 1]) % MOD;
    }
    S = 1;
    for (int i = SZ(A) - 1; i > 1; i--) {
        S = 1ll * S * A[i] % MOD;
        ret = (ret + 1ll * S * pd[i - 2] % MOD) % MOD;
    }
    return ret;
}

void dpDFS(int v, int p = -1) {
    vector<int> A;
    if (~p) {
        int pos = find(begin(vec[v]), end(vec[v]), up[v]) - begin(vec[v]);
        swap(vec[v][pos], vec[v].back());
    }
    for (int &u : vec[v]) {
        A.push_back(1);
        for (int &w : adj[u]) 
            if (w != p) dpDFS(w, v), A.back() = A.back() * 1ll * (dp2[w] + 1) % MOD;
    }
    dp[v] = calc_dp1(A);
    if (SZ(vec[v]) > 1) {
        int S = 1;
        for (int &x : A) 
            S = 1ll * S * x % MOD;
        dp[v] = (dp[v] - S + MOD) % MOD;
    }
    if (~p) {
        A.pop_back(); 
        dp2[v] = (dp[v] - calc_dp2(A) + MOD) % MOD;
    }
}

int main() {
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i++) 
        vec[i] = {i};
    for (int i = 1; i <= m; i++) {
        int u, v; scanf("%d%d", &u, &v);
        adj[fr[i] = u].push_back(i);
        adj[to[i] = v].push_back(i);
    }
    preDFS(1);
    for (int i = 1; i <= m; i++) {
        if (!B[i]) {
            int u = fr[i], v = to[i];
            Union(u, v);
        }
    }
    for (int i = 1; i <= n; i++) 
        Find(i);
    for (int i = 1; i <= n; i++) 
        if (!rt[i]) rt[i] = i;
    for (int i = 1; i <= n; i++) {
        vector<int> tm;
        for (int id : adj[i]) { 
            int u = fr[id] ^ to[id] ^ i;
            if (rt[i] != rt[u]) tm.push_back(rt[u]);
        }
        adj[i].swap(tm);
    }
    DFS(rt[1]);
    dpDFS(rt[1]);
    int ret = 0;
    for (int i = 1; i <= n; i++) 
        if (rt[i] == i) ret = (ret + dp[i]) % MOD;
    printf("%d\n", ret);
    return 0;
}

Compilation message

Main.cpp: In function 'int main()':
Main.cpp:103:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  103 |     scanf("%d%d", &n, &m);
      |     ~~~~~^~~~~~~~~~~~~~~~
Main.cpp:107:24: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  107 |         int u, v; scanf("%d%d", &u, &v);
      |                   ~~~~~^~~~~~~~~~~~~~~~

Subtask #1
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4940 KB Output is correct
2 Correct 3 ms 4940 KB Output is correct
3 Correct 3 ms 4940 KB Output is correct
4 Correct 3 ms 4940 KB Output is correct
5 Correct 3 ms 5012 KB Output is correct
6 Correct 3 ms 4940 KB Output is correct
7 Incorrect 3 ms 4992 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 3 ms 4940 KB Output is correct
2 Correct 14 ms 6092 KB Output is correct
3 Correct 180 ms 16416 KB Output is correct
4 Correct 197 ms 16408 KB Output is correct
5 Correct 189 ms 16416 KB Output is correct
6 Correct 158 ms 16408 KB Output is correct
7 Correct 256 ms 27588 KB Output is correct
8 Correct 220 ms 23456 KB Output is correct
9 Correct 186 ms 23492 KB Output is correct
10 Correct 137 ms 16964 KB Output is correct
11 Correct 147 ms 16660 KB Output is correct
12 Correct 163 ms 16480 KB Output is correct
13 Correct 180 ms 16324 KB Output is correct
14 Correct 166 ms 21752 KB Output is correct
15 Correct 189 ms 29380 KB Output is correct
16 Correct 205 ms 30916 KB Output is correct
17 Correct 177 ms 16528 KB Output is correct
18 Correct 171 ms 16344 KB Output is correct
19 Correct 180 ms 16324 KB Output is correct
20 Correct 125 ms 17004 KB Output is correct
21 Correct 127 ms 17012 KB Output is correct
22 Correct 118 ms 16864 KB Output is correct

Subtask #3
0 / 30.0

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

Subtask #4
0 / 50.0

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