Submission #999363

#TimeUsernameProblemLanguageResultExecution timeMemory
999363yoav_sStar Trek (CEOI20_startrek)C++17
0 / 100
1 ms348 KiB
#include <bits/stdc++.h> using namespace std; typedef long long 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); ll N, D; cin >> N >> D; vv graph(N); for (ll i= 0; i < N - 1; i++) { ll 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 << 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);
      |                      ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...