QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#291218 | #4811. Be Careful | Radewoosh# | WA | 1ms | 4412kb | C++23 | 4.2kb | 2023-12-26 06:50:33 | 2023-12-26 06:50:33 |
Judging History
answer
//~ while (clock()<=69*CLOCKS_PER_SEC)
//~ #pragma comment(linker, "/stack:200000000")
#pragma GCC optimize("O3")
//~ #pragma GCC target ("avx2")
//~ #pragma GCC optimize("Ofast")
//~ #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
//~ #pragma GCC optimize("unroll-loops")
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
using namespace std;
template <typename T>
using ordered_set =
tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
#define sim template < class c
#define ris return * this
#define dor > debug & operator <<
#define eni(x) sim > typename \
enable_if<sizeof dud<c>(0) x 1, debug&>::type operator<<(c i) {
sim > struct rge { c b, e; };
sim > rge<c> range(c i, c j) { return rge<c>{i, j}; }
sim > auto dud(c* x) -> decltype(cerr << *x, 0);
sim > char dud(...);
struct debug {
#ifdef LOCAL
~debug() { cerr << endl; }
eni(!=) cerr << boolalpha << i; ris; }
eni(==) ris << range(begin(i), end(i)); }
sim, class b dor(pair < b, c > d) {
ris << "(" << d.first << ", " << d.second << ")";
}
sim dor(rge<c> d) {
*this << "[";
for (auto it = d.b; it != d.e; ++it)
*this << ", " + 2 * (it == d.b) << *it;
ris << "]";
}
#else
sim dor(const c&) { ris; }
#endif
};
#define imie(...) " [" << #__VA_ARGS__ ": " << (__VA_ARGS__) << "] "
#define shandom_ruffle random_shuffle
using ll=long long;
using pii=pair<int,int>;
using pll=pair<ll,ll>;
using vi=vector<int>;
using vll=vector<ll>;
const int nax=207;
const ll mod=998244353;
//~ using bn=bitset<nax>;
const ll d=60;
struct bn
{
ll wek[2];
bn()
{
//~ wek.resize(4);
for (int i=0; i<2; i++)
wek[i]=0;
}
int daj(int v) const
{
return (wek[v/d]>>(v%d))&1;
}
void zapal(int v)
{
wek[v/d]|=(1LL<<(v%d));
}
};
struct MyHash { std::size_t operator()(bn x) const
{
ll ret=0;
for (int i=0; i<2; i++)
ret^=x.wek[i];
return ret;
} };
bool operator==(const bn& a, const bn& b)
{
for (int i=0; i<2; i++)
if (a.wek[i]!=b.wek[i])
return false;
return true;
}
int n;
vi graf[nax];
int naj[nax];
ll dp[nax][nax];
bn pus;
bool operator <(const bn &a, const bn &b)
{
//~ return a.wek<b.wek;
for (int i=0; i<2; i++)
if (a.wek[i]!=b.wek[i])
return a.wek[i]<b.wek[i];
return false;
}
int czylisc(int v)
{
return graf[v].empty();
}
int moge(int v, int co)
{
vi wek(co);
for (int i : graf[v])
wek[min(naj[i], co-1)]++;
for (int i=co-1; i; i--)
{
if (wek[i]>1)
{
wek[i-1]+=wek[i]-1;
wek[i]=1;
}
}
for (int i : wek)
if (!i)
return 0;
return 1;
}
void dfs0(int v, int oj)
{
for (int &i : graf[v])
{
if (i==oj)
{
swap(i, graf[v].back());
graf[v].pop_back();
break;
}
}
for (int i : graf[v])
dfs0(i, v);
if (czylisc(v))
{
naj[v]=n;
}
else
{
while(moge(v, naj[v]+1))
naj[v]++;
}
}
ll dppom[nax][nax];//iloma, iledziur
void dod(ll &a, ll b)
{
a=(a+b)%mod;
}
bool mniej(int a, int b)
{
return naj[a]>naj[b];
}
void dfs1(int v)
{
if (czylisc(v))
return;
for (int i : graf[v])
dfs1(i);
unordered_map<bn, ll, MyHash> now, sta;
int liscie=0;
now[pus]=1;
sort(graf[v].begin(), graf[v].end(), mniej);
for (int i : graf[v])
{
if (czylisc(i))
{
liscie++;
continue;
}
now.swap(sta);
now.clear();
for (int j=0; j<=naj[i]; j++)
{
int x=min(j, naj[v]+1);
for (auto l : sta)
{
bn trz=l.first;
trz.zapal(x);
dod(now[trz], l.second*dp[i][j]);
}
}
}
for (auto i : now)
{
int brak=0;
for (int j=0; j<=naj[v]; j++)
{
if (i.first.daj(j))
continue;
dod(dp[v][j], i.second*dppom[liscie][brak]);
brak++;
}
}
}
int main()
{
scanf("%d", &n);
for (int i=1; i<n; i++)
{
int a, b;
scanf("%d%d", &a, &b);
graf[a].push_back(b);
graf[b].push_back(a);
}
dfs0(1, 0);
dppom[0][0]=1;
for (int i=1; i<nax; i++)
{
dppom[i][0]=dppom[i-1][0]*n%mod;
for (int j=1; j<=i; j++)
dppom[i][j]=(dppom[i-1][j-1]*j+dppom[i-1][j]*(n-j))%mod;
}
dfs1(1);
for (int i=0; i<=n; i++)
printf("%lld\n", dp[1][i]);
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 4132kb
input:
5 1 2 1 3 2 4 2 5
output:
55 127 34 0 0 0
result:
ok 6 numbers
Test #2:
score: 0
Accepted
time: 1ms
memory: 4124kb
input:
8 1 2 1 3 1 4 1 5 1 6 6 7 6 8
output:
69632 265534 133905 47790 12636 1944 0 0 0
result:
ok 9 numbers
Test #3:
score: 0
Accepted
time: 1ms
memory: 4408kb
input:
3 1 2 2 3
output:
1 3 0 0
result:
ok 4 number(s): "1 3 0 0"
Test #4:
score: 0
Accepted
time: 0ms
memory: 4412kb
input:
2 1 2
output:
2 1 0
result:
ok 3 number(s): "2 1 0"
Test #5:
score: 0
Accepted
time: 0ms
memory: 4376kb
input:
10 1 8 1 9 6 1 2 1 1 4 1 10 1 5 7 1 3 1
output:
1755647 612579511 359376750 200038110 104287680 49974120 21379680 7771680 2177280 362880 0
result:
ok 11 numbers
Test #6:
score: 0
Accepted
time: 0ms
memory: 4132kb
input:
10 2 8 2 9 6 2 2 1 2 4 2 10 2 5 7 2 3 2
output:
114358881 100000000 0 0 0 0 0 0 0 0 0
result:
ok 11 numbers
Test #7:
score: 0
Accepted
time: 0ms
memory: 4152kb
input:
10 7 8 8 9 6 5 2 1 3 4 9 10 4 5 7 6 3 2
output:
10 1 0 0 0 0 0 0 0 0 0
result:
ok 11 numbers
Test #8:
score: 0
Accepted
time: 1ms
memory: 4120kb
input:
10 3 6 2 4 4 9 8 4 2 5 10 5 3 7 2 1 1 3
output:
27510 31142 102399 0 0 0 0 0 0 0 0
result:
ok 11 numbers
Test #9:
score: 0
Accepted
time: 0ms
memory: 4120kb
input:
14 10 3 6 2 2 8 3 13 1 3 1 2 3 14 4 2 9 3 12 3 2 5 7 2 11 3
output:
930962871 780146137 253920328 0 0 0 0 0 0 0 0 0 0 0 0
result:
ok 15 numbers
Test #10:
score: 0
Accepted
time: 1ms
memory: 4152kb
input:
20 7 6 2 6 5 1 17 12 9 13 12 18 3 2 9 1 2 1 12 6 10 9 14 2 4 1 6 8 11 2 16 9 13 19 8 15 20 5
output:
572808214 694156482 763085092 958730326 465749894 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
result:
ok 21 numbers
Test #11:
score: 0
Accepted
time: 1ms
memory: 4112kb
input:
21 6 12 11 13 1 7 8 14 1 18 5 4 1 2 16 11 21 1 9 10 15 17 1 9 1 8 1 20 1 3 1 4 19 16 11 1 15 10 3 6
output:
778184256 242901486 277265229 855621813 564317020 918444623 408876720 314039448 593931360 0 0 0 0 0 0 0 0 0 0 0 0 0
result:
ok 22 numbers
Test #12:
score: 0
Accepted
time: 1ms
memory: 4216kb
input:
22 20 21 9 12 6 10 19 10 16 10 10 11 8 7 13 12 21 22 19 20 14 13 7 6 8 9 15 14 2 5 18 6 5 6 3 2 16 17 2 1 3 4
output:
142157709 5878180 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
result:
ok 23 numbers
Test #13:
score: 0
Accepted
time: 0ms
memory: 4140kb
input:
23 6 10 4 2 6 9 15 20 10 15 3 6 17 23 1 3 16 22 19 14 17 12 7 11 18 13 11 16 5 3 8 5 10 14 8 12 9 13 4 7 1 2 15 21
output:
7619809 175546557 7936610 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
result:
ok 24 numbers
Test #14:
score: 0
Accepted
time: 1ms
memory: 4168kb
input:
24 7 10 2 5 2 1 17 20 1 4 16 13 7 4 19 16 23 20 11 8 10 13 1 3 22 19 5 8 3 6 17 14 21 18 24 21 18 15 9 6 9 12 14 11 15 12
output:
24 576 15025 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
result:
ok 25 numbers
Test #15:
score: 0
Accepted
time: 0ms
memory: 4404kb
input:
24 22 16 17 11 15 9 13 7 8 2 1 3 5 1 6 12 9 3 14 8 21 15 17 23 19 13 7 1 24 18 2 1 5 11 1 4 4 10 18 12 20 14 10 16 1 6
output:
24 7962624 236177977 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
result:
ok 25 numbers
Test #16:
score: -100
Wrong Answer
time: 1ms
memory: 4404kb
input:
200 1 199 95 1 1 75 177 1 66 1 157 1 85 1 1 193 1 26 8 1 38 1 151 1 1 56 63 1 1 138 1 59 190 1 1 36 1 120 156 1 115 1 1 118 171 1 6 1 113 1 20 1 83 1 1 176 33 1 153 1 1 169 22 1 1 159 1 27 87 1 1 129 1 44 174 1 1 93 77 1 1 122 1 125 1 23 1 81 112 1 173 1 1 51 32 1 96 1 184 1 116 1 67 1 1 94 1 104 19...
output:
211917199 369375874 201944418 582671162 183066248 639389350 952947539 137147613 216366713 398936459 73236543 354059031 727857197 121548413 610762100 573534011 706945631 286154195 226699593 267771858 823273748 233587424 176942776 226493975 707601105 339075191 694353149 944734662 932707579 934386415 4...
result:
wrong answer 121st numbers differ - expected: '693625848', found: '0'