QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#304754#7895. Graph Partitioning 2algotesterWA 28ms20084kbC++207.9kb2024-01-14 02:06:052024-01-14 02:06:05

Judging History

你现在查看的是最新测评结果

  • [2024-01-14 02:06:05]
  • 评测
  • 测评结果：WA
  • 用时：28ms
  • 内存：20084kb
查看
  • [2024-01-14 02:06:05]
  • 提交

answer

#define _CRT_SECURE_NO_WARNINGS
#pragma comment(linker, "/stack:16777216")
#include <string>
#include <vector>
#include <map>
#include <list>
#include <iterator>
#include <set>
#include <queue>
#include <iostream>
#include <sstream>
#include <stack>
#include <deque>
#include <cmath>  
#include <memory.h>
#include <cstdlib>
#include <cstdio>
#include <cctype>
#include <algorithm>
#include <utility>
#include <time.h>
#include <bitset>
#include <random>
using namespace std;

#define FOR(i, a, b) for(int i = (a); i < (b); ++i)
#define RFOR(i, b, a) for(int i = (b) - 1; i >= (a); --i)
#define ITER(it, a) for (__typeof(a.begin()) it = a.begin(); it != a.end(); it++)
#define FILL(A,value) memset(A,value,sizeof(A))

#define ALL(V) V.begin(), V.end()
#define SZ(V) (int)V.size()
#define PB push_back
#define MP make_pair
const double PI=acos(-1.0);

typedef long long Int;
typedef long long LL;
typedef unsigned long long UINT;
typedef vector <int> VI;
typedef pair <int, int> PII;
typedef pair <double, double> PDD;

const int INF = 1000 * 1000 * 1000 + 7;
const LL LINF = INF * (LL) INF;

const int MAX = 100007;
const int CNT = 21;
const int MAX2 = 24000000;
const int LEN = 21;
const int BASE = 1000000000;

const int MOD = 998244353;

int n, k;
VI G[MAX];
int C[MAX];
VI V[MAX];
VI P;
int Q[MAX];

int T[MAX][CNT];
int RS[MAX][CNT];
int X[MAX][CNT];

int TT[MAX][CNT][2];

void dfs(int v, int p)
{
  Q[v] = p;
  C[v] = 1;
  FOR (k,0,SZ(G[v]))
  {
    int to = G[v][k];
    if (to == p) continue;
    dfs(to, v);
    C[v] += C[to];
    V[v].PB(to);
  }

  P.PB(v);
}

void add(int& x, int y)
{
  x += y;
  if (x >= MOD) x -= MOD;
}

int solveSmall()
{
  FOR (i,0,n)
  {
    int v = P[i], s = 1;

    FOR (j,0,SZ(V[v])+1) 
      FOR (t,0,CNT)
        T[j][t] = 0;

    T[0][1] = 1;

    FOR (j,0,SZ(V[v]))
    {
      int to = V[v][j];

      FOR (t0,0,s+1)
        if (T[j][t0] != 0)
          FOR (t1,0,min(C[to], k)+1)
            if (t0+t1 <= k+1)
            {
              int d = (Int)RS[to][t1] * T[j][t0] % MOD;
              add(T[j+1][t0+t1], d);
            }

      s += C[to];
    }


    // FOR (t,0,k+2)
    //   cout << v << ' ' << t << ' ' << T[SZ(V[v])+1][t] << endl;

    // cout << endl;

    FOR (j,0,k+1)
      RS[v][j] = T[SZ(V[v])][j];
    add(RS[v][0], T[SZ(V[v])][k]);
    add(RS[v][0], T[SZ(V[v])][k+1]);
  }

  return RS[0][0];
}

int solveLarge()
{
  int res = 0;
  
  FOR (i,0,n)
  {
    int v = P[i];

    {
      int s = 0;
      FOR (j,0,SZ(V[v])+1)
        FOR (t,0,CNT)
          FOR (q,0,2)
              TT[j][t][q] = 0;

      TT[0][0][0] = 1;

      FOR (j,0,SZ(V[v]))
      {
        int to = V[v][j];

        FOR (t0,0,min(CNT, s/k+2))
        FOR (q0,0,2)
          if (TT[j][t0][q0] != 0)
            FOR (t1,0,min(CNT, C[to]/k+2))
              if (t0+t1 < CNT && t1 <= C[to])
              {
                int c0 = (s-t0) % k;
                int c1 = (C[to]-t1) % k;

                if (c0 == 0 && c1 > 0 && q0) continue;

                int q1 = q0;
                if (c1 != 0) q1 = 1;

                if (c0 + c1 <= k)
                {
                  int d = (Int)RS[to][t1] * TT[j][t0][q0] % MOD;
                  add(TT[j+1][t0+t1][q1], d);

                  // if (q0 == 0 && c1 == 0 && t0+t1+1 < CNT)
                  // {
                  //   int d = (Int)X[to][t1] * TT[j][t0][q0] % MOD;
                  //   add(TT[j+1][t0+t1][1], d);
                  // }
                }
              }

        s += C[to];
      }

      //cout << v << endl;

      // FOR (t,0,6)
      // FOR (q,0,2)
      //   cout << v << ' ' << t << ' ' << q << ' ' <<  TT[SZ(V[v])][t][q] << endl;
      

      FOR (j,0,CNT)
      {
        FOR (q,0,2)
        {
          int cc = C[v]-1;

          if (j > cc) continue;
          int t = (cc-j) % k;

          if (t > 0 && t < k-1)
            add(RS[v][j], TT[SZ(V[v])][j][q]);
          else
          if (t == k-1)
          {
            if (q)
            {
              add(RS[v][j], TT[SZ(V[v])][j][q]);

              if (Q[v] != -1 && j+1 < CNT)
              {
                add(X[v][j], TT[SZ(V[v])][j][q]);
              }

            //               if (Q[v] != -1 && SZ(V[Q[v]]) == 1)
            // {
            //   add(RS[Q[v]][j+1], TT[SZ(V[v])][j][q]);
            // }
            }
          }
          else
          if (t == 0)
          {
            if (!q)
              add(RS[v][j], TT[SZ(V[v])][j][q]);
            if (q && j+1 < CNT)
              add(RS[v][j+1], TT[SZ(V[v])][j][q]);
          }
        }
      }


      // FOR (p,0,SZ(V[v]))
      // {
      //   int to = V[v][j];
      //   int d = 0;
      //   if (C[to] >= j && (C[to] - j) % k == 0)
      //     d = RS[to][j-1];
      //   LL[j] = RS[to]
      // }
    }

    {
      int s = 0;
      FOR (j,0,SZ(V[v])+1)
        FOR (t,0,CNT)
          FOR (q,0,2)
              TT[j][t][q] = 0;

      TT[0][0][0] = 1;

      FOR (j,0,SZ(V[v]))
      {
        int to = V[v][j];

        FOR (t0,0,min(CNT, s/k+2))
        FOR (q0,0,2)
          if (TT[j][t0][q0] != 0)
            FOR (t1,0,min(CNT, C[to]/k+2))
              if (t0+t1 < CNT && t1 <= C[to])
              {
                int c1 = (C[to]-t1) % k;

                if (c1 != 0) continue;

                int q1 = q0;

                {
                  int d = (Int)RS[to][t1] * TT[j][t0][q0] % MOD;
                  add(TT[j+1][t0+t1][q1], d);
                }

                if (q0 == 0 && t0+t1+1 < CNT)
                {
                  int d = (Int)X[to][t1] * TT[j][t0][q0] % MOD;
                  add(TT[j+1][t0+t1+1][1], d);
                }
              }

        s += C[to];
      }

      // //cout << v << endl;

      // cout << X[4][1] << endl;

      // FOR (t,0,6)
      // FOR (q,0,2)
      //   cout << v << '+' << t << ' ' << q << ' ' <<  TT[SZ(V[v])][t][q] << endl;
      

      FOR (j,0,CNT)
      {
        add(RS[v][j], TT[SZ(V[v])][j][1]);
      }


      // FOR (p,0,SZ(V[v]))
      // {
      //   int to = V[v][j];
      //   int d = 0;
      //   if (C[to] >= j && (C[to] - j) % k == 0)
      //     d = RS[to][j-1];
      //   LL[j] = RS[to]
      // }
    }
  }

  FOR (i,0,CNT)
    if (i <= C[0] && (C[0]-i) % k == 0)
      add(res, RS[0][i]);

  return res;
}

VI GG[MAX];
vector<PII> E;
int U[MAX];

int dfs2(int v)
{
  int res = 1;
  U[v] = 1;

  FOR (i,0,SZ(GG[v]))
  {
    int to = GG[v][i];
    if (U[to] == 0)
    {
      res += dfs2(to);
    }
  }

  return res;
}

int brute()
{
  int res = 0;

  FOR (mask,0,(1 << SZ(E)))
  {
    FOR (i,0,n)
      GG[i].clear();


    FOR (j,0,SZ(E))
      if (mask & (1 << j))
      {
        GG[E[j].first].PB(E[j].second);
        GG[E[j].second].PB(E[j].first);
      }


    FOR (i,0,n) U[i] = 0;

    bool ok = 1;

    FOR (i,0,n)
      if (U[i] == 0)
      {
        int c = dfs2(i);
        if (c != k && c != k+1) ok = 0;
      }

    res += ok;
  }

  return res;
}

int main()
{
  int t;
  cin >> t;
  
  FOR (tt,0,t)
  {
    scanf("%d %d", &n, &k);

    FOR (i,0,n)
      G[i].clear();

    E.clear();

    FOR (i,0,n-1)
    {
      int u, v;
      scanf("%d %d", &u, &v);
      -- u;
      -- v;
      E.PB(MP(u, v));
      G[u].PB(v);
      G[v].PB(u);
    }

    FOR (i,0,n)
    {
      C[i] = 0;
      V[i].clear();

      FOR (j,0,CNT)
      {
        RS[i][j] = 0;
        X[i][j] = 0;
      }
    }

    P.clear();

    dfs(0, -1);

    int res = 0;

    if (k < max((int)pow(n, 0.25), 3))
    {
      res = solveSmall();
    }
    else
    {
      res = solveLarge();
    }

    printf("%d\n", res);

  }
  
  
  return 0;
}
源文件, 语言: C++20

詳細信息

Test #1:

score: 100
Accepted
time: 0ms
memory: 19840kb

input:

2
8 2
1 2
3 1
4 6
3 5
2 4
8 5
5 7
4 3
1 2
1 3
2 4

output:

2
1

result:

ok 2 lines

Test #2:

score: -100
Wrong Answer
time: 28ms
memory: 20084kb

input:

5550
13 4
10 3
9 1
10 8
3 11
8 5
10 7
9 6
13 5
9 7
2 7
5 12
4 8
8 2
4 1
3 4
7 8
2 5
6 7
4 8
2 3
11 1
11 10
1 4
9 10
8 4
3 6
5 7
6 1
10 2
11 7
11 1
17 2
14 16
13 15
17 3
15 11
1 6
13 2
13 17
4 8
14 10
8 14
14 5
9 12
14 2
12 17
17 6
15 7
14 6
2 14
2 13
2 4
8 4
3 11
7 3
14 1
11 9
13 3
5 10
6 8
3 10
14 ...

output:

0
3
112
0
1
0
1
0
0
0
1
0
1
0
0
1
0
140
0
0
0
814
1
6
1
1
2
2
0
612
0
1
0
0
0
1
1
0
0
121
4536
0
0
1718
0
0
1
0
444
1
1908
1813
3
74
0
1
0
46
0
0
0
0
0
0
0
0
0
1
0
1
1
1
239
0
0
0
1
0
0
0
1
0
1
0
0
1
1
0
0
0
1
0
0
0
48
0
2
0
0
0
1
364
0
206
0
0
76
0
1
0
0
2
0
1
2
0
0
1
0
0
4
0
1
1
0
0
1
1
1
0
0
1
1
...

result:

wrong answer 5274th lines differ - expected: '12164896', found: '12164895'
English 繁體中文 简体中文

伺服器時間: 2024-12-01 05:48:49 | 開源專案