Submission #856206

#TimeUsernameProblemLanguageResultExecution timeMemory
856206sofijavelkovskaStar Trek (CEOI20_startrek)C++14
7 / 100
2 ms3164 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) { for (auto y : adj[x]) dfs1(y, x); win1[x]=win0[x]; return; } if (!win1[x]) losechildren[t]=losechildren[t]-1; if (losechildren[t]==0) win1[t]=false; if (!win1[t]) losechildren[x]=losechildren[x]+1; if (losechildren[x]>0) win1[x]=true; 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, i; long long d, total; 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); //for (i=1; i<=n; i++) // win1[i]=dfs1(i, -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); /*for (i=1; i<=n; i++) cout << win0[i] << " "; cout << '\n'; for (i=1; i<=n; i++) cout << win1[i] << " "; cout << '\n';*/ //cout << win << " " << lose << " " << critical << '\n'; if (win0[1]) total=n*win+(n-critical)*lose; else total=critical*lose; 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...