oj.uz

Submission #1060555

# Submission time Handle Problem Language Result Execution time Memory
1060555 2024-08-15T17:12:28 Z vjudge1 Subtree (INOI20_subtree) C++14
12 / 100
 688 ms 1048580 KB 
#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
typedef long double ld;
#define pb push_back
#define pf push_front
#define fi first
#define se second
const ll mod = 1e9+7, mxn = 1e5+7;
ll n, m, pr[mxn], dp[mxn][2], mul[mxn<<1];
bool ck[mxn], vis[mxn];
vector<ll> cycle;
vector<vector<ll>> g(mxn);
void get_cycle(ll u, ll v)
{
    // cerr << u << '\n'; 
    cycle.pb(u); ck[u] = 1;
    if (u == v) return;
    get_cycle(pr[u],v);
}
void dfs(ll u, ll v)
{
    vis[u] = 1;
    for (ll i : g[u]) if (i != v) 
    {
        if (vis[i] && !cycle.size()) 
        {
            // cerr << u << ' ' << i << '\n';
            get_cycle(u,i);
        }
        else if (!vis[i])
        {
            pr[i] = u;
            dfs(i,u);
        }
    }
}
void dfs_dp(ll u, ll v)
{
    dp[u][1] = 1;
    for (ll i : g[u]) if (i != v && !ck[i])
    {
        dfs_dp(i,u);
        dp[u][1] *= dp[i][1]+1;
        dp[u][1] %= mod;
        dp[u][0] += (dp[i][0]+dp[i][1])%mod;
        if (dp[u][0] >= mod) dp[u][0] -= mod;
    }
}
ll bpow(ll a, ll b)
{
    if (!b) return 1;
    ll m = bpow(a,b/2);
    if (b&1) return (((m*m)%mod)*a)%mod;
    return (m*m)%mod;
}
signed main()
{
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    // freopen("test.inp","r",stdin); freopen("test.out","w",stdout); freopen("test.err","w",stderr);
    cin >> n >> m;
    for (ll i = 1; i <= m; i++)
    {
        ll a, b; cin >> a >> b;
        g[a].pb(b); g[b].pb(a);        
    }
    dfs(1,1);
    if (!cycle.size()) cycle.pb(1);
    for (ll i : cycle) dfs_dp(i,i);
    ll ans = 0, id = 0; mul[0] = 1;
    for (ll i : cycle)
    {
        ans += (dp[i][0]+dp[i][1])%mod;
        if (ans >= mod) ans -= mod;
        id++; mul[id] = dp[i][1];
    }
    n = cycle.size();
    for (ll i = n+1; i <= 2*n; i++) mul[i] = mul[i-n];
    for (ll i = 1; i <= 2*n; i++) mul[i] = (mul[i]*mul[i-1])%mod;
    queue<ll> q;
    ll s = 0;
    for (ll i = 0; i < n-2; i++) 
    {
        ll inv = bpow(mul[i],mod-2);
        q.push(inv); s += inv;
        if (s >= mod) s -= mod;
    }
    for (ll i = n-1; i <= 2*n-2; i++)
    {
        ans += (s*mul[i])%mod;
        if (ans >= mod) ans -= mod;
        s -= q.front(); q.pop();
        if (s < 0) s += mod;
        ll inv = bpow(mul[i-1],mod-2);
        q.push(inv); s += inv;
        if (s >= mod) s -= mod;
    }   
    cout << ans;
}

Subtask #1
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4700 KB Output is correct
2 Correct 2 ms 4700 KB Output is correct
3 Runtime error 688 ms 1048580 KB Execution killed with signal 9
4 Halted 0 ms 0 KB -

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4696 KB Output is correct
2 Correct 4 ms 5096 KB Output is correct
3 Correct 27 ms 10588 KB Output is correct
4 Correct 27 ms 10588 KB Output is correct
5 Correct 31 ms 10584 KB Output is correct
6 Correct 27 ms 10320 KB Output is correct
7 Correct 53 ms 14420 KB Output is correct
8 Correct 32 ms 13140 KB Output is correct
9 Correct 31 ms 13396 KB Output is correct
10 Correct 24 ms 11100 KB Output is correct
11 Correct 24 ms 10448 KB Output is correct
12 Correct 31 ms 9928 KB Output is correct
13 Correct 31 ms 9820 KB Output is correct
14 Correct 22 ms 12236 KB Output is correct
15 Correct 35 ms 15184 KB Output is correct
16 Correct 35 ms 15700 KB Output is correct
17 Correct 31 ms 10004 KB Output is correct
18 Correct 28 ms 9864 KB Output is correct
19 Correct 31 ms 9812 KB Output is correct
20 Correct 19 ms 10600 KB Output is correct
21 Correct 20 ms 10844 KB Output is correct
22 Correct 25 ms 10584 KB Output is correct

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4700 KB Output is correct
2 Correct 2 ms 4700 KB Output is correct
3 Runtime error 688 ms 1048580 KB Execution killed with signal 9
4 Halted 0 ms 0 KB -

Subtask #4
0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4700 KB Output is correct
2 Correct 2 ms 4700 KB Output is correct
3 Runtime error 688 ms 1048580 KB Execution killed with signal 9
4 Halted 0 ms 0 KB -