Submission #38413297

Source Code Expand

#include <bits/stdc++.h>
#define st first
#define nd second
#define db double
#define re register
#define pb push_back
#define mk make_pair
//#define int long long
#define ldb long double
#define pii pair<int, int>
#define ull unsigned long long
#define mst(a, b) memset(a, b, sizeof(a))
using namespace std;
const int N = 5e3 + 10, mod = 998244353;
inline int read()
{
  int s = 0, w = 1;
  char ch = getchar();
  while(ch < '0' || ch > '9') { if(ch == '-') w *= -1; ch = getchar(); }
  while(ch >= '0' && ch <= '9') s = s * 10 + ch - '0', ch = getchar();
  return s * w;
}
int n;
int siz[N], h[N], f[N][N], g[N][N]; //f[u][i] 表示节点 u 在集合中，子树 u 中含 i 个强联通分量的方案数，g 则是节点 u 不在集合中
vector<int> G[N];
inline int add(int x, int y) { return x + y >= mod ? x + y - mod : x + y; }
inline void DFS(int u, int fa)
{
  g[u][0] = f[u][1] = 1, siz[u] = 1;
  for(re int to : G[u]){
    if(to == fa) continue;
    DFS(to, u);
    for(re int i = 0; i <= siz[u] + siz[to]; i++) h[i] = 0;
    for(re int i = 0; i <= siz[u]; i++) //枚举总的连通块数量
      for(re int j = 0; j <= siz[to]; j++) //枚举新加入的连通块数量
        h[i + j] = add(h[i + j], 1ll * g[u][i] * add(g[to][j], f[to][j]) % mod);
    for(re int i = 0; i <= siz[u] + siz[to]; i++) g[u][i] = h[i];
    for(re int i = 0; i <= siz[u] + siz[to]; i++) h[i] = 0;
    for(re int i = 0; i <= siz[u]; i++)
      for(re int j = 0; j <= siz[to]; j++)
        h[i + j] = add(h[i + j], 1ll * f[u][i] * f[to][j + 1] % mod), h[i + j] = add(h[i + j], 1ll * f[u][i] * g[to][j] % mod); //j + 1 是因为有一个连通块与 u 连在一起
    for(re int i = 0; i <= siz[u] + siz[to]; i++) f[u][i] = h[i];
    siz[u] += siz[to];
    
  }
}
signed main()
{
  n = read();
  for(re int i = 1, x, y; i < n; i++)
    x = read(), y = read(), G[x].pb(y), G[y].pb(x);
  DFS(1, 0);
  for(re int i = 1; i <= n; i++) printf("%lld\n", add(f[1][i], g[1][i]));
  return 0;
}

Submission Info

Submission Time
Task F - Components
User Booksnow
Language C++ (GCC 9.2.1)
Score 500
Code Size 2029 Byte
Status AC
Exec Time 226 ms
Memory 138276 KiB

Compile Error

./Main.cpp: In function ‘void DFS(int, int)’:
./Main.cpp:30:14: warning: ISO C++17 does not allow ‘register’ storage class specifier [-Wregister]
   30 |   for(re int to : G[u]){
      |              ^~
./Main.cpp:33:16: warning: ISO C++17 does not allow ‘register’ storage class specifier [-Wregister]
   33 |     for(re int i = 0; i <= siz[u] + siz[to]; i++) h[i] = 0;
      |                ^
./Main.cpp:34:16: warning: ISO C++17 does not allow ‘register’ storage class specifier [-Wregister]
   34 |     for(re int i = 0; i <= siz[u]; i++) //枚举总的连通块数量
      |                ^
./Main.cpp:35:18: warning: ISO C++17 does not allow ‘register’ storage class specifier [-Wregister]
   35 |       for(re int j = 0; j <= siz[to]; j++) //枚举新加入的连通块数量
      |                  ^
./Main.cpp:37:16: warning: ISO C++17 does not allow ‘register’ storage class specifier [-Wregister]
   37 |     for(re int i = 0; i <= siz[u] + siz[to]; i++) g[u][i] = h[i];
      |                ^
./Main.cpp:38:16: warning: ISO C++17 does not allow ‘register’ storage class specifier [-Wregister]
   38 |     for(re int i = 0; i <= siz[u] + siz[to]; i++) h[i] = 0;
      |                ^
./Main.cpp:39:16: warning: ISO C++17 does not allow ‘register’ storage class specifier [-Wregister]
   39 |     for(re int i = 0; i <= siz[u]; i++)
      |                ^
./Main.cpp:40:18: warning: ISO C++17 does not allow ‘register’ storage class specifier [-Wregister]
   40 |       for(re int j = 0; j <= siz[to]; j++)
      |                  ^
./Main.cpp:42:16: warning: ISO C++17 does not allow ‘register’ storage class specifier [-Wregister]
   42 |     for(re int i = 0; i <= siz[u] + siz[to]; i++) f[u][i] = h[i];
      |                ^
./Main.cpp: In function ‘int main()’:
./Main.cpp:50:14: warning: ISO C++17 does not allow ‘register’ storage class specifier [-Wregister]
   50 |   for(re int i = 1, x, y; i < n; i++)
      |              ^
./Main.cpp:50:21: warning: ISO C++17 d...

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 500 / 500
Status
AC × 3
AC × 54
Set Name Test Cases
Sample 00_sample_00.txt, 00_sample_01.txt, 00_sample_02.txt
All 00_sample_00.txt, 00_sample_01.txt, 00_sample_02.txt, 01_srnd_00.txt, 01_srnd_01.txt, 01_srnd_02.txt, 01_srnd_03.txt, 01_srnd_04.txt, 01_srnd_05.txt, 01_srnd_06.txt, 01_srnd_07.txt, 02_rnd_00.txt, 02_rnd_01.txt, 02_rnd_02.txt, 02_rnd_03.txt, 02_rnd_04.txt, 02_rnd_05.txt, 02_rnd_06.txt, 02_rnd_07.txt, 03_path_00.txt, 03_path_01.txt, 03_path_02.txt, 03_path_03.txt, 04_star_00.txt, 04_star_01.txt, 04_star_02.txt, 04_star_03.txt, 05_caterpillar_00.txt, 05_caterpillar_01.txt, 05_caterpillar_02.txt, 05_caterpillar_03.txt, 05_caterpillar_04.txt, 05_caterpillar_05.txt, 05_caterpillar_06.txt, 05_caterpillar_07.txt, 05_caterpillar_08.txt, 05_caterpillar_09.txt, 05_caterpillar_10.txt, 05_caterpillar_11.txt, 05_caterpillar_12.txt, 05_caterpillar_13.txt, 06_bintree_00.txt, 06_bintree_01.txt, 06_bintree_02.txt, 06_bintree_03.txt, 06_bintree_04.txt, 06_bintree_05.txt, 06_bintree_06.txt, 06_bintree_07.txt, 07_sqrt_00.txt, 07_sqrt_01.txt, 07_sqrt_02.txt, 07_sqrt_03.txt, 08_one_00.txt
Case Name Status Exec Time Memory
00_sample_00.txt AC 8 ms 3868 KiB
00_sample_01.txt AC 2 ms 3656 KiB
00_sample_02.txt AC 2 ms 3724 KiB
01_srnd_00.txt AC 2 ms 3712 KiB
01_srnd_01.txt AC 2 ms 3696 KiB
01_srnd_02.txt AC 2 ms 3804 KiB
01_srnd_03.txt AC 2 ms 3824 KiB
01_srnd_04.txt AC 2 ms 3780 KiB
01_srnd_05.txt AC 2 ms 3736 KiB
01_srnd_06.txt AC 2 ms 4016 KiB
01_srnd_07.txt AC 2 ms 3964 KiB
02_rnd_00.txt AC 99 ms 44372 KiB
02_rnd_01.txt AC 98 ms 44276 KiB
02_rnd_02.txt AC 97 ms 44360 KiB
02_rnd_03.txt AC 95 ms 43952 KiB
02_rnd_04.txt AC 100 ms 44184 KiB
02_rnd_05.txt AC 96 ms 44176 KiB
02_rnd_06.txt AC 96 ms 44184 KiB
02_rnd_07.txt AC 97 ms 44416 KiB
03_path_00.txt AC 225 ms 138276 KiB
03_path_01.txt AC 173 ms 102004 KiB
03_path_02.txt AC 225 ms 138020 KiB
03_path_03.txt AC 226 ms 138052 KiB
04_star_00.txt AC 184 ms 43856 KiB
04_star_01.txt AC 183 ms 43916 KiB
04_star_02.txt AC 138 ms 43852 KiB
04_star_03.txt AC 138 ms 43796 KiB
05_caterpillar_00.txt AC 109 ms 46868 KiB
05_caterpillar_01.txt AC 144 ms 67104 KiB
05_caterpillar_02.txt AC 189 ms 89964 KiB
05_caterpillar_03.txt AC 188 ms 95824 KiB
05_caterpillar_04.txt AC 191 ms 86552 KiB
05_caterpillar_05.txt AC 146 ms 67124 KiB
05_caterpillar_06.txt AC 103 ms 46916 KiB
05_caterpillar_07.txt AC 99 ms 45880 KiB
05_caterpillar_08.txt AC 104 ms 49196 KiB
05_caterpillar_09.txt AC 159 ms 91036 KiB
05_caterpillar_10.txt AC 138 ms 75504 KiB
05_caterpillar_11.txt AC 99 ms 47244 KiB
05_caterpillar_12.txt AC 101 ms 46624 KiB
05_caterpillar_13.txt AC 98 ms 46572 KiB
06_bintree_00.txt AC 96 ms 44216 KiB
06_bintree_01.txt AC 95 ms 44380 KiB
06_bintree_02.txt AC 71 ms 36808 KiB
06_bintree_03.txt AC 73 ms 37068 KiB
06_bintree_04.txt AC 72 ms 36992 KiB
06_bintree_05.txt AC 72 ms 37108 KiB
06_bintree_06.txt AC 73 ms 37312 KiB
06_bintree_07.txt AC 73 ms 37380 KiB
07_sqrt_00.txt AC 105 ms 43876 KiB
07_sqrt_01.txt AC 104 ms 43860 KiB
07_sqrt_02.txt AC 103 ms 44044 KiB
07_sqrt_03.txt AC 106 ms 43936 KiB
08_one_00.txt AC 2 ms 3684 KiB