oj.uz

Submission #919915

# Submission time Handle Problem Language Result Execution time Memory
919915 2024-02-01T20:36:30 Z CyberCow Star Trek (CEOI20_startrek) C++17
45 / 100
 70 ms 25668 KB 
#include <random>
#include <algorithm>
#include <bitset>
#include <chrono>
#include <cmath>
#include <deque>
#include <fstream>
#include <iomanip>
#include <iostream>
#include <iterator>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <vector>
#include <chrono>
#define m_p make_pair
#define all(x) (x).begin(),(x).end()
#define sz(x) ((x).size())
typedef long long ll;
using namespace std;
mt19937 rnd(348502);
const ll N = 100010;
ll mod = 1e9 + 7;

ll binpow(ll a, ll x)
{
    if (x == 0)
        return 1;
    if (x % 2)
        return (a * binpow(a, x - 1)) % mod;
    return binpow((a * a) % mod, x / 2);
}

vector<ll> v[N];
ll dp[N][2];
ll dpv[N][2];

void Dfs(ll g, ll p)
{
    ll qan = 0, qan1 = 0, sz = 0;
    for (auto to : v[g])
    {
        if (to != p)
        {
            sz++;
            Dfs(to, g);
            if (dp[to][0])
                qan++;
            if (dp[to][1] == 1)
                qan1++;
        }
    }
    if (qan != sz)
    {
        dp[g][1] = 1;
    }
    if (qan1 != sz)
    {
        dp[g][0] = 1;
    }
}

void Dfs1(ll g, ll p, ll a, ll b)
{
    ll qan = a, qan1 = b, sz = v[g].size();
    for (auto to : v[g])
    {
        if (to != p)
        {
            qan += dp[to][0];
            qan1 += dp[to][1];
        }
    }
    if (qan != sz)
    {
        dpv[g][1] = 1;
    }
    if (qan1 != sz)
    {
        dpv[g][0] = 1;
    }
    for (auto to : v[g])
    {
        if(to != p)
        Dfs1(to, g, (qan1 - dp[to][1] != sz - 1), (qan - dp[to][0] != sz - 1));
    }
}

ll q0q0 = 0, q0q1 = 0, q1q0 = 0, q1q1 = 0;

ll dpans[N][2][2][2];

void Dfs2(ll g, ll p)
{
    ll qan = 0, qan1 = 0, sz = 0;
    for (auto to : v[g])
    {
        if (to != p)
        {
            sz++;
            Dfs2(to, g);
            if (dpans[to][0][0][1] == 1)
                qan++;
            if (dpans[to][0][1][1] == 1)
                qan1++;
        }
    }
    if (qan != sz)
    {
        dpans[g][0][1][1] = 1;
        dpans[g][1][1][1] += q1q0;
        dpans[g][1][1][1] += q1q1;
    }
    else
    {
        dpans[g][0][1][0] = 1;
        dpans[g][1][1][0] += q1q0;
        dpans[g][1][1][0] += q1q1;
    }
    if (qan1 != sz)
    {
        dpans[g][0][0][1] = 1;
        dpans[g][1][0][1] += q0q1;
        dpans[g][1][0][1] += q1q1;
    }
    else
    {
        dpans[g][0][0][0] = 1;
        dpans[g][1][0][0] += q0q1;
        dpans[g][1][0][0] += q1q1;
    }
    dpans[g][1][0][1] += q0q0;
    dpans[g][1][1][1] += q0q0;
    dpans[g][1][0][1] += q1q0;
    dpans[g][1][1][1] += q0q1;
    for (auto to : v[g])
    {
        if (to != p)
        {
            ll kop = qan;
            ll kop1 = qan1;
            kop -= dpans[to][0][0][1];
            kop1 -= dpans[to][0][1][1];
            if (kop != sz - 1)
            {
                dpans[g][1][1][1] += dpans[to][1][0][1];
                dpans[g][1][1][1] += dpans[to][1][0][0];
            }
            else
            {
                dpans[g][1][1][0] += dpans[to][1][0][1];
                dpans[g][1][1][1] += dpans[to][1][0][0];
            }
            if (kop1 != sz - 1)
            {
                dpans[g][1][0][1] += dpans[to][1][1][1];
                dpans[g][1][0][1] += dpans[to][1][1][0];
            }
            else
            {
                dpans[g][1][0][0] += dpans[to][1][1][1];
                dpans[g][1][0][1] += dpans[to][1][1][0];
            }
            dpans[g][1][1][1] %= mod;
            dpans[g][1][1][0] %= mod;
            dpans[g][1][0][1] %= mod;
            dpans[g][1][0][0] %= mod;
            dpans[g][0][1][1] %= mod;
            dpans[g][0][1][0] %= mod;
            dpans[g][0][0][1] %= mod;
            dpans[g][0][0][0] %= mod;
        }
    }
}

void solve()
{
    ll n, d, x, y;
    cin >> n >> d;
    if (n == 2)
    {
        for (ll i = 0; i < n - 1; i++)
        {
            cin >> x >> y;
        }
        cout << binpow(4, d);
    }
    else
    {
        for (ll i = 0; i < n - 1; i++)
        {
            cin >> x >> y;
            v[x].push_back(y);
            v[y].push_back(x);
        }
        Dfs(1, -1);
        Dfs1(1, -1, 0, 0);
        for (ll i = 1; i <= n; i++)
        {
            if (dpv[i][0] == 1 && dpv[i][1] == 1)
            {
                q1q1++;
            }
            if (dpv[i][0] == 0 && dpv[i][1] == 1)
            {
                q0q1++;
            }
            if (dpv[i][0] == 1 && dpv[i][1] == 0)
            {
                q1q0++;
            }
            if (dpv[i][0] == 0 && dpv[i][1] == 0)
            {
                q0q0++;
            }
        }
        Dfs2(1, -1);
        cout << dpans[1][1][1][1] % mod;
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    ll tt = 1;
    //cout << (mod + -10000010 % mod) % mod;
    //cin >> tt;
    while (tt--) {
        solve();
    }
    return 0;
}

Subtask #1
0.0 / 0.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 5724 KB Output is correct
2 Incorrect 2 ms 5980 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 3676 KB Output is correct
2 Correct 2 ms 3872 KB Output is correct
3 Correct 1 ms 3676 KB Output is correct
4 Correct 1 ms 3676 KB Output is correct
5 Correct 1 ms 3676 KB Output is correct

Subtask #3
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 5724 KB Output is correct
2 Correct 2 ms 5724 KB Output is correct
3 Correct 2 ms 5724 KB Output is correct
4 Correct 2 ms 5724 KB Output is correct
5 Correct 2 ms 5724 KB Output is correct
6 Correct 2 ms 5724 KB Output is correct

Subtask #4
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 5724 KB Output is correct
2 Correct 2 ms 5724 KB Output is correct
3 Correct 2 ms 5724 KB Output is correct
4 Correct 2 ms 5724 KB Output is correct
5 Correct 2 ms 5724 KB Output is correct
6 Correct 2 ms 5724 KB Output is correct
7 Correct 2 ms 5980 KB Output is correct
8 Correct 3 ms 5980 KB Output is correct
9 Correct 2 ms 5980 KB Output is correct
10 Correct 2 ms 5980 KB Output is correct
11 Correct 3 ms 5980 KB Output is correct

Subtask #5
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 5724 KB Output is correct
2 Correct 2 ms 5724 KB Output is correct
3 Correct 2 ms 5724 KB Output is correct
4 Correct 2 ms 5724 KB Output is correct
5 Correct 2 ms 5724 KB Output is correct
6 Correct 2 ms 5724 KB Output is correct
7 Correct 2 ms 5980 KB Output is correct
8 Correct 3 ms 5980 KB Output is correct
9 Correct 2 ms 5980 KB Output is correct
10 Correct 2 ms 5980 KB Output is correct
11 Correct 3 ms 5980 KB Output is correct
12 Correct 57 ms 20816 KB Output is correct
13 Correct 70 ms 25668 KB Output is correct
14 Correct 41 ms 16464 KB Output is correct
15 Correct 46 ms 16724 KB Output is correct
16 Correct 48 ms 16724 KB Output is correct

Subtask #6
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 5724 KB Output is correct
2 Correct 2 ms 5724 KB Output is correct
3 Correct 2 ms 5724 KB Output is correct
4 Correct 2 ms 5724 KB Output is correct
5 Correct 2 ms 5724 KB Output is correct
6 Correct 2 ms 5724 KB Output is correct
7 Correct 2 ms 5980 KB Output is correct
8 Correct 3 ms 5980 KB Output is correct
9 Correct 2 ms 5980 KB Output is correct
10 Correct 2 ms 5980 KB Output is correct
11 Correct 3 ms 5980 KB Output is correct
12 Correct 2 ms 5724 KB Output is correct
13 Incorrect 2 ms 5980 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #7
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 5724 KB Output is correct
2 Correct 2 ms 5724 KB Output is correct
3 Correct 2 ms 5724 KB Output is correct
4 Correct 2 ms 5724 KB Output is correct
5 Correct 2 ms 5724 KB Output is correct
6 Correct 2 ms 5724 KB Output is correct
7 Correct 2 ms 5980 KB Output is correct
8 Correct 3 ms 5980 KB Output is correct
9 Correct 2 ms 5980 KB Output is correct
10 Correct 2 ms 5980 KB Output is correct
11 Correct 3 ms 5980 KB Output is correct
12 Correct 57 ms 20816 KB Output is correct
13 Correct 70 ms 25668 KB Output is correct
14 Correct 41 ms 16464 KB Output is correct
15 Correct 46 ms 16724 KB Output is correct
16 Correct 48 ms 16724 KB Output is correct
17 Correct 2 ms 5724 KB Output is correct
18 Incorrect 2 ms 5980 KB Output isn't correct
19 Halted 0 ms 0 KB -

Subtask #8
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 5724 KB Output is correct
2 Incorrect 2 ms 5980 KB Output isn't correct
3 Halted 0 ms 0 KB -