Submission #856816

#TimeUsernameProblemLanguageResultExecution timeMemory
856816sofijavelkovskaStar Trek (CEOI20_startrek)C++14
45 / 100
75 ms15476 KiB
#include <bits/stdc++.h> using namespace std; const int MAXN=1e5, MOD=1e9+7; vector<int> adj[MAXN+1]; bool win0[MAXN+1], win1[MAXN+1]; int losechildren[MAXN+1]; long long power4(long long n) { long long result=1, current=4; for (long long i=0; i<64; i++) { if (n&((long long)1<<i)) result=result*current%MOD; current=current*current%MOD; } return result; } bool dfs0(int x, int t) { bool possible=false; for (auto y : adj[x]) { if (y==t) continue; if (!dfs0(y, x)) possible=true; } return win0[x]=possible; } void dfs1(int x, int t) { if (t==-1) { win1[x]=win0[x]; for (auto y : adj[x]) { if (y==t) continue; dfs1(y, x); } return; } int memox=losechildren[x]; int memot=losechildren[t]; if (!win0[x]) losechildren[t]=losechildren[t]-1; if (losechildren[t]==0) losechildren[x]=losechildren[x]+1; if (losechildren[x]>0) win1[x]=true; else win1[x]=false; for (auto y : adj[x]) { if (y==t) continue; dfs1(y, x); } losechildren[x]=memox; losechildren[t]=memot; return; } int dfscritical(int x, int t) { int critical=0; if (!win0[x]) { critical=critical+1; for (auto y : adj[x]) { if (y==t) continue; critical=critical+dfscritical(y, x); } } else { int losenodes=0; for (auto y : adj[x]) { if (y==t) continue; if (!win0[y]) { critical=critical+dfscritical(y, x); losenodes=losenodes+1; } } if (losenodes>1) critical=0; } return critical; } void countlosechildren(int x, int t) { losechildren[x]=0; for (auto y : adj[x]) { if (y==t) continue; countlosechildren(y, x); if (!win0[y]) losechildren[x]=losechildren[x]+1; } return; } int main() { ios_base::sync_with_stdio(0); cin.tie(0); int n, x, y, total, i; long long d; cin >> n >> d; for (i=0; i<n-1; i++) { cin >> x >> y; adj[x].push_back(y); adj[y].push_back(x); } if (n==2) { cout << power4(d); return 0; } dfs0(1, -1); countlosechildren(1, -1); dfs1(1, -1); int win=0; for (i=1; i<=n; i++) if (win1[i]) win=win+1; int lose=n-win; int critical=dfscritical(1, -1); if (win0[1]) total=((long long)n*win+(long long)(n-critical)*lose)%MOD; else total=(long long)critical*lose%MOD; cout << total; return 0; }
#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...