Submission #795462

#	Time	Username	Problem	Language	Result	Execution time	Memory
795462		MISM06	Subtree (INOI20_subtree)	C++14	100 / 100	144 ms	33108 KiB

Main

#include<bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair < int , int > pii;
typedef pair < int , pii > piii;
typedef pair < ll , ll > pll;
typedef pair < ll , pll > plll;
#define pb  push_back
#define all(x)  x.begin(), x.end()
#define sze     size()
#define F first
#define S second
#define kids    int mid = (tl + tr) >> 1, cl = v << 1, cr = v << 1 | 1;
#define wall__ cout << "________________________________________\n";

const ll N = 1e5 + 10, mod = 1e9 + 7;

inline void add (ll &x, ll y) {
    x += y; if (x >= mod) x -= mod;
    if (x < 0) x += mod;
}
inline ll Sum (ll x, ll y) {
    x += y; if (x >= mod) x -= mod;
    if (x < 0) x += mod;
    return x;
}
inline ll mul (ll x, ll y) {
    return x * y % mod;
}

int n, m, par[N], beg[N], h[N], id[N];
vector < int > g[N];
bool mark[N];
ll dp[N], pd[N];
vector < ll > pre[N], suf[N];

void dfs0 (int v, int p) {
    par[v] = p;
    mark[v] = 1;
    h[v] = h[p] + 1;
    for (int i = 0; i < g[v].sze; i++) {
        int u = g[v][i];
        if (u == p) continue;
        if (mark[u]) {
            beg[v] = u;
            continue;
        }
        id[u] = i;
        dfs0(u, v);
    }
}

ll get (int v, int i) {
    if (g[v].sze == 1) return 1;
    if (i == 0) return suf[v][1];
    if (i == g[v].sze - 1)  return pre[v][i - 1];
    return mul(pre[v][i - 1], suf[v][i + 1]);
}

void dfs1 (int v, int p) {
    for (auto u : g[v]) {
        if (par[u] != v) {
            pre[v].pb(1);
            suf[v].pb(1);
            continue;
        }
        dfs1(u, v);
        pre[v].pb(dp[u] + 1);
        suf[v].pb(dp[u] + 1); 
    }
    // cout << v << " : \n";
    for (int i = 0; i < g[v].sze; i++) {
        if (i == 0) continue;
        pre[v][i] = mul(pre[v][i - 1], pre[v][i]);
    }
    for (int i = g[v].sze - 1; i >= 0; --i) {
        if (i == g[v].sze - 1) continue;
        suf[v][i] = mul(suf[v][i + 1], suf[v][i]);
    }
    
    if (h[beg[v]] < h[v]) {
        dp[v] = suf[v][0];
        return;
    }
    int b = beg[v];
    
    pd[b] = dp[b];
    int x = par[b], y = b;
    while (h[x] >= h[v]) {
        pd[x] = mul(pd[y], get(x, id[y]));
        y = x; x = par[x];
    }
    vector < int > o;
    o.pb(b);
    x = par[b]; y = b;
    while (h[x] >= h[v]) {
        o.pb(x);
        add(pd[x], pd[y]);
        y = x; x = par[x];
    }
    ll res = 0, t = 0;
    ll s = 1;
    for (int i = o.sze - 1; i >= 1; --i) {
        int x = o[i], y = o[i - 1];
        s = mul(s, get(x, id[y]));
        add(t, s);
        if (i > 1) add(res, mul(s, pd[o[i - 2]]));
    }
    add(dp[v], t);
    // cout << "res = " << res << '\n';
    add(dp[v], res);

}

void solve () {
    
    cin >> n >> m;
    for (int i = 1; i <= m; i++) {
        int v, u; cin >> v >> u;
        g[v].pb(u);
        g[u].pb(v);
    }
    if (n == 1) {
        cout << 1 << '\n';
        return;
    }
    dfs0(1, 0);
    dfs1(1, 0);
    // cout << "dp : "; for (int i = 1; i <= n; i++) cout << dp[i] << " ";
    // cout << '\n';
    ll ans = 0;
    for (int i = 1; i <= n; i++) add(ans, dp[i]);
    cout << ans << '\n';

}   

int main() {
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    solve();
    return 0;
}

Compilation message (stderr)

Main.cpp: In function 'void dfs0(int, int)':
Main.cpp:42:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   42 |     for (int i = 0; i < g[v].sze; i++) {
      |                       ^
Main.cpp: In function 'll get(int, int)':
Main.cpp:57:11: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   57 |     if (i == g[v].sze - 1)  return pre[v][i - 1];
      |         ~~^~~~~~~~~~~~~~~
Main.cpp: In function 'void dfs1(int, int)':
Main.cpp:73:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   73 |     for (int i = 0; i < g[v].sze; i++) {
      |                       ^
Main.cpp:78:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   78 |         if (i == g[v].sze - 1) continue;
      |             ~~^~~~~~~~~~~~~~~

• Subtask 1: 8 / 8
• Subtask 2: 12 / 12
• Subtask 3: 30 / 30
• Subtask 4: 50 / 50