QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #304756 | #7895. Graph Partitioning 2 | algotester | Compile Error | / | / | C++20 | 7.8kb | 2024-01-14 02:09:16 | 2024-01-14 02:09:17 |
Judging History
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;
}
Details
answer.code:1:1: error: ‘define’ does not name a type
1 | define _CRT_SECURE_NO_WARNINGS
| ^~~~~~
In file included from /usr/include/c++/11/bits/stl_algobase.h:62,
from /usr/include/c++/11/bits/char_traits.h:39,
from /usr/include/c++/11/string:40,
from answer.code:3:
/usr/include/c++/11/ext/type_traits.h:162:35: error: ‘bool __gnu_cxx::__is_null_pointer’ redeclared as different kind of entity
162 | __is_null_pointer(std::nullptr_t)
| ^
/usr/include/c++/11/ext/type_traits.h:157:5: note: previous declaration ‘template<class _Type> bool __gnu_cxx::__is_null_pointer(_Type)’
157 | __is_null_pointer(_Type)
| ^~~~~~~~~~~~~~~~~
/usr/include/c++/11/ext/type_traits.h:162:26: error: ‘nullptr_t’ is not a member of ‘std’
162 | __is_null_pointer(std::nullptr_t)
| ^~~~~~~~~
In file included from /usr/include/c++/11/bits/move.h:57,
from /usr/include/c++/11/bits/stl_pair.h:59,
from /usr/include/c++/11/bits/stl_algobase.h:64,
from /usr/include/c++/11/bits/char_traits.h:39,
from /usr/include/c++/11/string:40,
from answer.code:3:
/usr/include/c++/11/type_traits:200:27: error: ‘size_t’ has not been declared
200 | template <typename _Tp, size_t = sizeof(_Tp)>
| ^~~~~~
/usr/include/c++/11/type_traits:405:26: error: ‘std::size_t’ has not been declared
405 | template<typename _Tp, std::size_t _Size>
| ^~~
/usr/include/c++/11/type_traits:406:25: error: ‘_Size’ was not declared in this scope
406 | struct is_array<_Tp[_Size]>
| ^~~~~
/usr/include/c++/11/type_traits:406:31: error: template argument 1 is invalid
406 | struct is_array<_Tp[_Size]>
| ^
/usr/include/c++/11/type_traits:511:42: error: ‘nullptr_t’ is not a member of ‘std’
511 | struct __is_null_pointer_helper<std::nullptr_t>
| ^~~~~~~~~
/usr/include/c++/11/type_traits:511:51: error: template argument 1 is invalid
511 | struct __is_null_pointer_helper<std::nullptr_t>
| ^
/usr/include/c++/11/type_traits:1311:37: error: ‘size_t’ is not a member of ‘std’
1311 | : public integral_constant<std::size_t, alignof(_Tp)>
| ^~~~~~
/usr/include/c++/11/type_traits:1311:57: error: template argument 1 is invalid
1311 | : public integral_constant<std::size_t, alignof(_Tp)>
| ^
/usr/include/c++/11/type_traits:1320:37: error: ‘size_t’ is not a member of ‘std’
1320 | : public integral_constant<std::size_t, 0> { };
| ^~~~~~
/usr/include/c++/11/type_traits:1320:46: error: template argument 1 is invalid
1320 | : public integral_constant<std::size_t, 0> { };
| ^
/usr/include/c++/11/type_traits:1322:26: error: ‘std::size_t’ has not been declared
1322 | template<typename _Tp, std::size_t _Size>
| ^~~
/usr/include/c++/11/type_traits:1323:21: error: ‘_Size’ was not declared in this scope
1323 | struct rank<_Tp[_Size]>
| ^~~~~
/usr/include/c++/11/type_traits:1323:27: error: template argument 1 is invalid
1323 | struct rank<_Tp[_Size]>
| ^
/usr/include/c++/11/type_traits:1324:37: error: ‘size_t’ is not a member of ‘std’
1324 | : public integral_constant<std::size_t, 1 + rank<_Tp>::value> { };
| ^~~~~~
/usr/include/c++/11/type_traits:1324:65: error: template argument 1 is invalid
1324 | : public integral_constant<std::size_t, 1 + rank<_Tp>::value> { };
| ^
/usr/include/c++/11/type_traits:1328:37: error: ‘size_t’ is not a member of ‘std’
1328 | : public integral_constant<std::size_t, 1 + rank<_Tp>::value> { };
| ^~~~~~
/usr/include/c++/11/type_traits:1328:65: error: template argument 1 is invalid
1328 | : public integral_constant<std::size_t, 1 + rank<_Tp>::value> { };
| ^
/usr/include/c++/11/type_traits:1333:37: error: ‘size_t’ is not a member of ‘std’
1333 | : public integral_constant<std::size_t, 0> { };
| ^~~~~~
/usr/include/c++/11/type_traits:1333:46: error: template argument 1 is invalid
1333 | : public integral_constant<std::size_t, 0> { };
| ^
/usr/include/c++/11/type_traits:1335:42: error: ‘std::size_t’ has not been declared
1335 | template<typenam...