Submission #999366

#	Time	Username	Problem	Language	Result	Execution time	Memory
999366		yoav_s	Star Trek (CEOI20_startrek)	C++17	0 / 100	0 ms	348 KiB

startrek

#include <bits/stdc++.h>

using namespace std;

typedef __int128 ll;
typedef vector<ll> v;
typedef vector<v> vv;
typedef vector<vv> vvv;
typedef pair<ll,ll> p;
typedef vector<p> vp;
typedef vector<vp> vvp;
typedef vector<vvp> vvvp;
typedef pair<ll, p> tri;
typedef vector<tri> vtri;
typedef vector<vtri> vvtri;
typedef vector<vvtri> vvvtri;
typedef vector<bool> vb;
typedef vector<vb> vvb;
typedef vector<vvb> vvvb;

#define f first
#define s second
#define pb push_back
#define eb emplace_back
#define all(v) (v).begin(),(v).end()

const ll INF = 1e18;
const ll mod = 1e9 + 7;

ll modPow(ll a, ll b)
{
    if (b == 0) return 1;
    ll res = modPow(a, b / 2);
    res = (res * res) % mod;
    if (b % 2 == 1) res = (res * a) % mod;
    return res;
}

void getWinningStates(ll i, vv &graph, vb &winning, vb &visited)
{
    if (visited[i]) return;
    visited[i] = true;
    for (ll x : graph[i])
    {
        if (!visited[x])
        {
            getWinningStates(x, graph, winning, visited);
            if (!winning[x]) winning[i] = true;
        }
    }
}

ll getSubtreeSize(ll i, vv &graph, v &res)
{
    if (res[i] != 0) return 0;
    res[i] = 1;
    for (ll x : graph[i]) res[i] += getSubtreeSize(x, graph, res);
    return res[i];
}

ll solve(ll i, vv &graph, vb &isWinning, v &res, vb &visited, bool shouldWin, v &subtreeSize, ll winningCount, ll losingCount)
{
    ll N = graph.size();
    if (visited[i]) return 0;
    visited[i] = true;
    if (shouldWin)
    {
        if (isWinning[i])
        {
            ll losingChildren = 0;
            ll losingChild;
            for (ll x : graph[i])
                if (!visited[x] && !isWinning[x])
                {
                    losingChildren++;
                    losingChild = x;
                }
            if (losingChildren == 1)
            {
                res[i] += (N * (subtreeSize[i] - subtreeSize[losingChild])) % mod;
                res[i] += solve(losingChild, graph, isWinning, res, visited, false, subtreeSize, winningCount, losingCount);
                res[i] %= mod;
                return res[i];
            }
            else
            {
                res[i] = (N * subtreeSize[i]) % mod;
                return res[i];
            }
        }
        else
        {
            res[i] += losingCount;
            for (ll x : graph[i])
            {
                if (!visited[x])
                {
                    res[i] += solve(x, graph, isWinning, res, visited, false, subtreeSize, winningCount, losingCount);
                }
            }
            res[i] %= mod;
            return res[i];
        }
    }
    else
    {
        //should be losing - all children should be winning
        if (!isWinning[i])
        {
            res[i] += winningCount;
            for (ll x : graph[i])
            {
                if (!visited[x])
                    res[i] += solve(x, graph, isWinning, res, visited, true, subtreeSize, winningCount, losingCount);
            }
            res[i] %= mod;
            return res[i];
        }
        else
        {
            ll losingChildren = 0, losing;
            for (ll x : graph[i])
            {
                if (!visited[x] && !isWinning[x])
                {
                    losingChildren++; losing = x;
                }
            }
            if (losingChildren > 1) return 0;
            res[i] = solve(losing, graph, isWinning, res, visited, true, subtreeSize, winningCount, losingCount);
            return res[i];
        }
    }
}

int main()
{
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    long long N, D;
    cin >> N >> D;
    vv graph(N);
    for (ll i=  0; i < N - 1; i++)
    {
        long long a, b;
        cin >> a >> b;
        a--; b--;
        graph[a].pb(b);
        graph[b].pb(a);
    }
    vb isWinning(N), visited(N, false);
    getWinningStates(0, graph, isWinning, visited);
    ll winningCount = 0, losingCount = 0;
    for (auto x : isWinning)
    {
        if (x) winningCount++;
        else losingCount++;
    }
    v subtreeSize(N, 0);
    getSubtreeSize(0, graph, subtreeSize);
    v dp(N, 0);
    visited = vb(N, false);
    solve(0, graph, isWinning, dp, visited, true, subtreeSize, winningCount, losingCount);
    cout << (long long)dp[0] << "\n";
    return 0;
}

Compilation message (stderr)

startrek.cpp: In function 'll solve(ll, vv&, vb&, v&, vb&, bool, v&, ll, ll)':
startrek.cpp:130:27: warning: 'losing' may be used uninitialized in this function [-Wmaybe-uninitialized]
  130 |             res[i] = solve(losing, graph, isWinning, res, visited, true, subtreeSize, winningCount, losingCount);
      |                      ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 0 / 0
• Subtask 2: 0 / 7
• Subtask 3: 0 / 8
• Subtask 4: 0 / 15
• Subtask 5: 0 / 15
• Subtask 6: 0 / 20
• Subtask 7: 0 / 20
• Subtask 8: 0 / 15