QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#874182 | #6362. Accommodation Plan | handongheng | WA | 478ms | 23080kb | C++20 | 4.2kb | 2025-01-27 18:31:51 | 2025-01-27 18:31:52 |
Judging History
answer
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
#define bst __gnu_pbds::tree<ll, __gnu_pbds::null_type, less<ll>, \
__gnu_pbds::rb_tree_tag, \
__gnu_pbds::tree_order_statistics_node_update>
typedef long long ll;
typedef pair<ll, ll> pii;
const int N = 1e5 + 5, mod = 1e9 + 7;
vector<pii> e[N];
int vcnt[N], siz[N], tsiz, rt, maxsiz[N], n, k;
ll dis[N], L;
bool vis[N];
void chmax(int &a, int b)
{
a = max(a, b);
}
void getrt(int u, int fa)
{
siz[u] = 1;
for (pii x : e[u])
{
ll v, w;
tie(v, w) = x;
if (!vis[v] && v != fa)
{
getrt(v, u);
siz[u] += siz[v];
chmax(maxsiz[u], siz[v]);
}
}
chmax(maxsiz[u], tsiz - siz[u]);
if (maxsiz[u] < maxsiz[rt])
rt = u;
}
vector<ll> dist;
vector<int> s;
void getdis(int u, int fa)
{
dist.push_back(dis[u]);
s.push_back(u);
for (pii x : e[u])
{
int v, w;
tie(v, w) = x;
if (!vis[v] && v != fa)
{
dis[v] = dis[u] + w;
getdis(v, u);
}
}
}
void cal(int u, ll d, int upd)
{
dist.clear();
s.clear();
dis[u] = 0;
getdis(u, 0);
sort(dist.begin(), dist.end());
for (int v : s)
{
auto pos = upper_bound(dist.begin(), dist.end(), d - dis[v]);
int k = pos - dist.begin();
vcnt[v] += upd * k;
}
}
void dfs(int u)
{
vis[u] = 1;
cal(u, L, 1);
for (pii x : e[u])
{
ll v, w;
tie(v, w) = x;
if (!vis[v])
{
cal(v, L - 2 * w, -1);
}
}
for (pii x : e[u])
{
ll v, w;
tie(v, w) = x;
if (!vis[v])
{
tsiz = siz[v], rt = 0;
getrt(v, u);
dfs(rt);
}
}
}
ll frac[N];
void init()
{
frac[0] = 1;
for (int i = 1; i <= n; ++i)
{
(frac[i] = frac[i - 1] * i) %= mod;
}
}
ll qpow(ll a, ll b)
{
ll ret = 1;
for (; b; b >>= 1, (a *= a) %= mod)
{
if (b & 1)
(ret *= a) %= mod;
}
return ret;
}
ll C(int i, int j)
{
if (i < j)
return 0;
return ((frac[i] * qpow(frac[i - j], mod - 2)) % mod * qpow(frac[j], mod - 2)) % mod;
}
bst tr;
int son[N], idfn[N], dfn[N], cnt;
ll wf[N];
void getson(int u, int fa)
{
dfn[u] = ++cnt, idfn[cnt] = u;
siz[u] = 1;
for (pii x : e[u])
{
ll v, w;
tie(v, w) = x;
if (v != fa)
{
dis[v] = dis[u] + w;
wf[v] = w;
getson(v, u);
if (siz[son[u]] < siz[v])
son[u] = v;
siz[u] += siz[v];
}
}
}
void color(int u, bool typ)
{
if (typ == 1)
{
for (int i = dfn[u]; i <= dfn[u] + siz[u] - 1; ++i)
tr.insert(dis[idfn[i]]);
}
else
{
for (int i = dfn[u]; i <= dfn[u] + siz[u] - 1; ++i)
tr.erase(dis[idfn[i]]);
}
}
ll ans;
void solve(int u, int fa)
{
(ans += C(vcnt[u], k)) %= mod;
for (pii x : e[u])
{
ll v, w;
tie(v, w) = x;
if (v != son[u] && v != fa)
{
solve(v, u);
color(v, 1);
}
}
if (son[u])
solve(son[u], u);
if (u != 1)
{
int c1 = tr.order_of_key(dis[u] + L + 1), c2 = tr.order_of_key(dis[u] + L - wf[u] + 1);
(ans -= C(vcnt[u] - c1 + c2, k) - mod) %= mod;
}
tr.insert(dis[u]);
if (son[fa] != u)
{
color(u, 0);
}
}
signed main()
{
ios::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
cin >> n >> k >> L;
for (int i = 1; i < n; ++i)
{
ll u, v, w;
cin >> u >> v >> w;
e[u].emplace_back(v, w);
e[v].emplace_back(u, w);
}
init();
getrt(1, 0);
tsiz = siz[1];
maxsiz[0] = 1e9, rt = 0;
getrt(1, 0);
dfs(rt);
getson(1, 0);
tr.clear();
solve(1, 0);
cout << (ans * frac[k]) % mod << '\n';
return 0;
}
详细
Test #1:
score: 100
Accepted
time: 0ms
memory: 5836kb
input:
5 2 7 1 2 4 3 2 8 2 4 2 4 5 6
output:
12
result:
ok 1 number(s): "12"
Test #2:
score: 0
Accepted
time: 478ms
memory: 23080kb
input:
100000 6851 454171387 1 2 699608 2 3 27930 3 4 719630 4 5 1020888 2 6 763543 6 7 351259 4 8 486314 2 9 1387365 6 10 1288357 4 11 545529 11 12 516390 7 13 222352 12 14 1374608 13 15 118475 13 16 65492 15 17 924923 3 18 1143588 6 19 441762 12 20 1196602 17 21 1406265 15 22 865475 17 23 897062 21 24 35...
output:
95272333
result:
ok 1 number(s): "95272333"
Test #3:
score: 0
Accepted
time: 0ms
memory: 7908kb
input:
8 6 737945515 6 4 3454 6 5 39228 6 8 90331 6 7 31904 6 2 64718 6 3 69991 6 1 58925
output:
20160
result:
ok 1 number(s): "20160"
Test #4:
score: 0
Accepted
time: 0ms
memory: 7912kb
input:
8 5 573891853 8 3 845070 8 1 2304293 8 2 7165015 8 5 8512198 8 6 4711032 8 7 8764253 8 4 5876665
output:
6720
result:
ok 1 number(s): "6720"
Test #5:
score: 0
Accepted
time: 0ms
memory: 5704kb
input:
8 8 672635007 7 3 975710134 7 6 618246273 7 8 903412606 7 4 267301617 7 2 151872591 7 1 678749289 7 5 945399588
output:
0
result:
ok 1 number(s): "0"
Test #6:
score: 0
Accepted
time: 1ms
memory: 7864kb
input:
8 3 3095530 2 4 6015 2 3 2822 2 6 6598 2 1 8970 2 8 4664 2 7 7370 2 5 1425
output:
336
result:
ok 1 number(s): "336"
Test #7:
score: 0
Accepted
time: 0ms
memory: 7784kb
input:
8 6 19228 6 7 60 6 2 61 6 3 48 6 8 50 6 4 31 6 1 80 6 5 74
output:
20160
result:
ok 1 number(s): "20160"
Test #8:
score: 0
Accepted
time: 0ms
memory: 7784kb
input:
8 1 9476 8 3 21 8 4 20 8 7 32 8 6 44 8 5 5 8 2 4 8 1 49
output:
8
result:
ok 1 number(s): "8"
Test #9:
score: 0
Accepted
time: 0ms
memory: 7784kb
input:
8 8 762771948 3 6 67798 6 5 29033 5 1 46925 1 4 63404 4 2 62686 2 7 28707 7 8 43653
output:
40320
result:
ok 1 number(s): "40320"
Test #10:
score: 0
Accepted
time: 0ms
memory: 7908kb
input:
8 6 236053664 8 6 7426363 6 5 4228183 5 2 8931107 2 3 2377463 3 4 7969748 4 7 6516277 7 1 869296
output:
20160
result:
ok 1 number(s): "20160"
Test #11:
score: 0
Accepted
time: 0ms
memory: 5740kb
input:
8 3 895307116 8 1 562601320 1 6 995045068 6 7 762245166 7 4 900560333 4 2 904657319 2 3 693933408 3 5 740726094
output:
6
result:
ok 1 number(s): "6"
Test #12:
score: 0
Accepted
time: 0ms
memory: 5692kb
input:
8 6 6478494 6 4 7929 4 7 7277 7 3 4616 3 8 3211 8 1 5309 1 5 3659 5 2 8934
output:
20160
result:
ok 1 number(s): "20160"
Test #13:
score: 0
Accepted
time: 0ms
memory: 5704kb
input:
8 8 98347 5 3 71 3 2 78 2 7 70 7 4 1 4 8 49 8 1 25 1 6 22
output:
40320
result:
ok 1 number(s): "40320"
Test #14:
score: 0
Accepted
time: 0ms
memory: 7908kb
input:
8 8 1021 3 7 8 7 8 39 8 5 49 5 4 20 4 1 5 1 2 22 2 6 44
output:
40320
result:
ok 1 number(s): "40320"
Test #15:
score: 0
Accepted
time: 0ms
memory: 7776kb
input:
8 2 937341485 3 4 10326 3 8 38111 4 2 94903 8 7 27951 2 6 87423 7 1 71485 6 5 54079
output:
56
result:
ok 1 number(s): "56"
Test #16:
score: 0
Accepted
time: 0ms
memory: 7780kb
input:
8 8 163056691 7 3 6152073 7 2 5986799 3 6 1018535 2 5 6195760 6 1 4076813 5 4 6053416 1 8 610159
output:
40320
result:
ok 1 number(s): "40320"
Test #17:
score: 0
Accepted
time: 0ms
memory: 7780kb
input:
8 6 972755033 8 5 76876568 5 1 326110430 1 6 533819049 6 2 512217855 2 4 268926040 4 3 536052600 3 7 585723821
output:
720
result:
ok 1 number(s): "720"
Test #18:
score: 0
Accepted
time: 0ms
memory: 7868kb
input:
8 1 9861459 7 2 4835 7 3 2634 2 6 156 3 4 9057 6 8 1437 4 1 6443 8 5 5528
output:
8
result:
ok 1 number(s): "8"
Test #19:
score: 0
Accepted
time: 0ms
memory: 5824kb
input:
8 1 68953 8 7 87 8 1 93 7 4 59 1 2 76 4 5 74 2 3 75 5 6 54
output:
8
result:
ok 1 number(s): "8"
Test #20:
score: 0
Accepted
time: 0ms
memory: 7908kb
input:
8 7 9862 3 7 8 3 5 8 7 1 35 5 8 14 1 2 44 8 4 35 2 6 45
output:
40320
result:
ok 1 number(s): "40320"
Test #21:
score: 0
Accepted
time: 0ms
memory: 5836kb
input:
8 4 962167918 3 6 132 6 8 62001 8 5 26403 5 7 93215 7 2 13434 2 1 56213 1 4 70902
output:
1680
result:
ok 1 number(s): "1680"
Test #22:
score: 0
Accepted
time: 0ms
memory: 7776kb
input:
8 1 825218502 2 5 8075962 5 4 7818298 4 7 4883799 7 8 4487180 8 3 1828837 3 6 6013343 6 1 5936665
output:
8
result:
ok 1 number(s): "8"
Test #23:
score: -100
Wrong Answer
time: 0ms
memory: 7912kb
input:
8 1 50202950 2 7 598899556 2 5 889975695 7 8 462045061 7 3 559969878 5 1 138885967 5 6 331379106 8 4 477174698
output:
3
result:
wrong answer 1st numbers differ - expected: '8', found: '3'