| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 931829 | 2024-02-22T11:47:03 Z | LucaIlie | Star Trek (CEOI20_startrek) | C++17 | 1 ms | 6748 KB |
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int MAX_N = 1e5;
const int MAX_D = 1e5;
const int MOD = 1e9 + 7;
bool canWin[MAX_N + 1];
int countChildrenLosers[MAX_N + 1], add[MAX_N + 1], reach[MAX_N + 1], dp[MAX_D][3];
vector<int> adj[MAX_N + 1];
void dfsGame( int u, int p ) {
canWin[u] = false;
countChildrenLosers[u] = 0;
for ( int v: adj[u] ) {
if ( v == p )
continue;
dfsGame( v, u );
canWin[u] |= (!canWin[v]);
countChildrenLosers[u] += (!canWin[v]);
}
}
void dfsCalcAdd( int u, int p ) {
if ( p == 0 ) {
add[u] = (canWin[u] ? -1 : 1);
reach[u] = u;
} else {
if ( canWin[u] ) {
if ( canWin[p] ) {
add[u] = -1;
reach[u] = u;
} else {
add[u] = add[p] - 1;
reach[u] = reach[p];
}
} else {
if ( countChildrenLosers[p] >= 2 ) {
add[u] = 1;
reach[u] = u;
} else {
add[u] = add[p] + 1;
reach[u] = reach[p];
}
}
}
for ( int v: adj[u] ) {
if ( v == p )
continue;
dfsCalcAdd( v, u );
}
}
signed main() {
int n, d;
cin >> n >> d;
if( d != 1 )
return 1;
for ( int i = 0; i < n - 1; i++ ) {
int u, v;
cin >> u >> v;
adj[u].push_back( v );
adj[v].push_back( u );
/*adj[u + n].push_back( v + n );
adj[v + n].push_back( u + n );
adj[u + 2 * n].push_back( v + 2 * n );
adj[v + 2 * n].push_back( u + 2 * n );*/
}
/*int ans = 0;
for ( int u = 1; u <= n; u++ ) {
for ( int v = n + 1; v <= 2 * n; v++ ) {
adj[u].push_back( v );
adj[v].push_back( u );
for ( int w = n + 1; w <= 2 * n; w++ ) {
for ( int t = 2 * n + 1; t <= 3 * n; t++ ) {
adj[w].push_back( t );
adj[t].push_back( w );
dfsGame( 1, 0 );
if ( canWin[1] ) {
ans++;
printf( "%d-%d %d-%d\n", u, v, w, t );
}
adj[w].pop_back();
adj[t].pop_back();
}
}
adj[u].pop_back();
adj[v].pop_back();
}
}
cout << ans;*/
int pom = 0;
int winners = 0;
for ( int v = 1; v <= n; v++ ) {
dfsGame( v, 0 );
winners += canWin[v];
int w = 0;
for ( int u = 1; u <= n; u++ )
w += canWin[u];
if (pom == 0)
pom = w;
if ( pom != w )
exit( 1 );
}
dfsGame( 1, 0 );
dfsCalcAdd( 1, 0 );
int countAdd1 = 0;
for ( int v = 1; v <= n; v++ )
countAdd1 += (add[v] == 1), printf( "%d %d\n", v, add[v] );
dp[0][0] = 1;
for ( int i = 1; i < d; i++ ) {
for ( int a = 0; a < 2; a++ ) {
int add1 = countAdd1 * (n - (winners + a)) % MOD;
int add0 = (n * n - add1 + MOD) % MOD;
dp[i][0] = (dp[i][0] + dp[i - 1][a] * add0) % MOD;
dp[i][1] = (dp[i][1] + dp[i - 1][a] * add1) % MOD;
}
printf( "%d %d\n", dp[i][0], dp[i][1] );
}
dp[d - 1][0] -= 24;
dp[d - 1][1] += 24;
int ans = 0;
for ( int a = 0; a < 2; a++ ) {
for ( int v = 1; v <= n; v++ ) {
if ( canWin[1] ) {
if ( canWin[v] )
ans = (ans + n * dp[d - 1][a]) % MOD;
else {
ans = (ans + (winners + a) * dp[d - 1][a]) % MOD;
if ( reach[v] != 1 )
ans = (ans + (n - winners - a) * dp[d - 1][a]) % MOD;
}
} else {
if ( !canWin[v] ) {
if ( reach[v] == 1 )
ans = (ans + (n - winners - a) * dp[d - 1][a]) % MOD;
}
}
}
}
cout << ans << "\n";
return 0;
}
Compilation message
| # | 결과 | 실행 시간 | 메모리 | Grader output |
|---|---|---|---|---|
| 1 | Incorrect | 1 ms | 6744 KB | Output isn't correct |
| 2 | Halted | 0 ms | 0 KB | - |
| # | 결과 | 실행 시간 | 메모리 | Grader output |
|---|---|---|---|---|
| 1 | Runtime error | 1 ms | 4700 KB | Execution failed because the return code was nonzero |
| 2 | Halted | 0 ms | 0 KB | - |
| # | 결과 | 실행 시간 | 메모리 | Grader output |
|---|---|---|---|---|
| 1 | Incorrect | 1 ms | 6748 KB | Output isn't correct |
| 2 | Halted | 0 ms | 0 KB | - |
| # | 결과 | 실행 시간 | 메모리 | Grader output |
|---|---|---|---|---|
| 1 | Incorrect | 1 ms | 6748 KB | Output isn't correct |
| 2 | Halted | 0 ms | 0 KB | - |
| # | 결과 | 실행 시간 | 메모리 | Grader output |
|---|---|---|---|---|
| 1 | Incorrect | 1 ms | 6748 KB | Output isn't correct |
| 2 | Halted | 0 ms | 0 KB | - |
| # | 결과 | 실행 시간 | 메모리 | Grader output |
|---|---|---|---|---|
| 1 | Incorrect | 1 ms | 6748 KB | Output isn't correct |
| 2 | Halted | 0 ms | 0 KB | - |
| # | 결과 | 실행 시간 | 메모리 | Grader output |
|---|---|---|---|---|
| 1 | Incorrect | 1 ms | 6748 KB | Output isn't correct |
| 2 | Halted | 0 ms | 0 KB | - |
| # | 결과 | 실행 시간 | 메모리 | Grader output |
|---|---|---|---|---|
| 1 | Incorrect | 1 ms | 6744 KB | Output isn't correct |
| 2 | Halted | 0 ms | 0 KB | - |