QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#874182#6362. Accommodation PlanhandonghengWA 478ms23080kbC++204.2kb2025-01-27 18:31:512025-01-27 18:31:52

Judging History

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

  • [2025-01-27 18:31:52]
  • 评测
  • 测评结果:WA
  • 用时:478ms
  • 内存:23080kb
  • [2025-01-27 18:31:51]
  • 提交

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'