UOJ Logo

NOI.AC

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#213299#3849. 旅行日记1811260623140320ms26948kbC++112.6kb2024-11-10 12:50:072024-11-10 13:08:53

answer

#include <bits/stdc++.h>
#define int long long
using namespace std;
int n, st, u, v, head[400001], pos, f[200001], siz[200001], ans[200001], sum[200001];
struct edge
{
    int u, v, next;
} e[400001];
void add(int u, int v)
{
    e[++pos] = {u, v, head[u]};
    head[u] = pos;
}
vector<int> a[200001];
int read()
{
    int x = 0, f = 1;
    char c = getchar();
    while (c < '0' || c > '9')
    {
        if (c == '-')
            f = -1;
        c = getchar();
    }
    while (c >= '0' && c <= '9')
    {
        x = (x << 1) + (x << 3) + (c ^ 48);
        c = getchar();
    }
    return x * f;
}
void dfs(int x)
{
    vector<pair<double, int>> aa;
    for (auto y : a[x])
    {
        dfs(y);
        aa.emplace_back((double)sum[y] / siz[y], y);
    }
    sort(aa.begin(), aa.end());
    for (auto y : aa)
    {
        ans[x] += siz[x] * sum[y.second] + ans[y.second];
        siz[x] += siz[y.second];
        sum[x] += sum[y.second];
    }
}
void solve()
{
    int vis[11], maxn = 0;
    vis[1] = st;
    bool viss[11];
    for (int i = 1; i <= n; i++)
    {
        if (i == st)
            continue;
        if (i < st)
            vis[i + 1] = i;
        else
            vis[i] = i;
    }
    
    do
    {
        int ans = 0;
        memset(viss, 0, sizeof(viss));
        if (vis[1] != st)
            break;
        //cout<<"yuanshen\n";
        for (int i = 1; i <= n; i++)
        {
            viss[vis[i]] = true;
            ans += vis[i] * i;
            //cout<<vis[i]<<' '<<f[vis[i]]<<ans<<endl;
            if(i==1)
                continue;
            if (!viss[f[vis[i]]])
            {
                ans = -1e18;
                break;
            }
        }
        maxn = max(maxn, ans);
    } while (next_permutation(vis + 1, vis + n + 1));
    printf("%lld", maxn);
}
void dfss(int u, int fa)
{
    if (fa)
    {
        f[u] = fa;
        a[fa].push_back(u);
    }
    // cout<<fa<<' '<<u<<endl;
    for (int i = head[u]; i; i = e[i].next)
    {
        int v = e[i].v;
        if (v == fa)
            continue;
        dfss(v, u);
    }
}
signed main()
{
    n = read();
    st = read();
    for (int i = 1; i <= n; i++)
    {
        ans[i] = sum[i] = i;
        siz[i] = 1;
    }
    for (int i = 2; i <= n; i++)
    {
        u = read();
        v = read();
        add(u, v);
        add(v, u);
    }
    dfss(st, 0);
    if (n > 18)
    {
        dfs(st);
        printf("%lld\n", ans[st]);
    }
    else
    {
        solve();
    }
    return 0;
}

详细

小提示:点击横条可展开更详细的信息

Test #1:

score: 5
Accepted
time: 2ms
memory: 5916kb

input:

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

output:

304

result:

ok 1 number(s): "304"

Test #2:

score: 5
Accepted
time: 0ms
memory: 5916kb

input:

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

output:

345

result:

ok 1 number(s): "345"

Test #3:

score: 5
Accepted
time: 6ms
memory: 5916kb

input:

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

output:

320

result:

ok 1 number(s): "320"

Test #4:

score: 5
Accepted
time: 5ms
memory: 5912kb

input:

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

output:

336

result:

ok 1 number(s): "336"

Test #5:

score: 0
Time Limit Exceeded

input:

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

output:


result:


Test #6:

score: 0
Time Limit Exceeded

input:

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

output:


result:


Test #7:

score: 0
Time Limit Exceeded

input:

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

output:


result:


Test #8:

score: 0
Time Limit Exceeded

input:

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

output:


result:


Test #9:

score: 5
Accepted
time: 4ms
memory: 17196kb

input:

100000 16441
1 2
1 3
1 4
1 5
1 6
1 7
1 8
1 9
1 10
1 11
1 12
1 13
1 14
1 15
1 16
1 17
1 18
1 19
1 20
...

output:

333338198204980

result:

ok 1 number(s): "333338198204980"

Test #10:

score: 5
Accepted
time: 8ms
memory: 17200kb

input:

100000 99177
1 2
1 3
1 4
1 5
1 6
1 7
1 8
1 9
1 10
1 11
1 12
1 13
1 14
1 15
1 16
1 17
1 18
1 19
1 20
...

output:

333333415360924

result:

ok 1 number(s): "333333415360924"

Test #11:

score: 5
Accepted
time: 10ms
memory: 17196kb

input:

100000 59601
1 2
1 3
1 4
1 5
1 6
1 7
1 8
1 9
1 10
1 11
1 12
1 13
1 14
1 15
1 16
1 17
1 18
1 19
1 20
...

output:

333336557240200

result:

ok 1 number(s): "333336557240200"

Test #12:

score: 5
Accepted
time: 9ms
memory: 17196kb

input:

100000 30655
1 2
1 3
1 4
1 5
1 6
1 7
1 8
1 9
1 10
1 11
1 12
1 13
1 14
1 15
1 16
1 17
1 18
1 19
1 20
...

output:

333337863500815

result:

ok 1 number(s): "333337863500815"

Test #13:

score: 0
Wrong Answer
time: 32ms
memory: 26516kb

input:

100000 53503
15420 17742
17742 64232
64232 17523
17523 33388
33388 73908
73908 15412
15412 67920
679...

output:

250355925087320

result:

wrong answer 1st numbers differ - expected: '250413064505673', found: '250355925087320'

Test #14:

score: 0
Wrong Answer
time: 37ms
memory: 25376kb

input:

100000 5700
95638 43692
43692 52040
52040 29909
29909 66571
66571 20077
20077 28853
28853 20470
2047...

output:

250311236792275

result:

wrong answer 1st numbers differ - expected: '250814390051272', found: '250311236792275'

Test #15:

score: 0
Wrong Answer
time: 30ms
memory: 26948kb

input:

100000 73165
7735 42311
42311 26035
26035 44914
44914 71359
71359 9414
9414 21996
21996 19789
19789 ...

output:

249920916430743

result:

wrong answer 1st numbers differ - expected: '249949750624627', found: '249920916430743'

Test #16:

score: 0
Wrong Answer
time: 34ms
memory: 22760kb

input:

100000 81023
86193 9869
9869 79475
79475 88553
88553 54043
54043 91736
91736 23883
23883 68360
68360...

output:

250257297095145

result:

wrong answer 1st numbers differ - expected: '250402679195507', found: '250257297095145'

Test #17:

score: 0
Wrong Answer
time: 34ms
memory: 16724kb

input:

100000 53752
20439 68430
24723 68430
12283 20439
7861 12283
73785 68430
44056 24723
22482 7861
44454...

output:

252077000601581

result:

wrong answer 1st numbers differ - expected: '296233806565812', found: '252077000601581'

Test #18:

score: 0
Wrong Answer
time: 44ms
memory: 16796kb

input:

100000 81174
36555 78900
68651 36555
12967 78900
43832 36555
12851 36555
63272 43832
23048 12967
355...

output:

253164911305232

result:

wrong answer 1st numbers differ - expected: '296033950451487', found: '253164911305232'

Test #19:

score: 0
Wrong Answer
time: 26ms
memory: 16748kb

input:

100000 2143
44484 44643
28626 44484
80384 44643
33549 44484
89306 44643
57164 44484
73721 44643
4818...

output:

252335286139049

result:

wrong answer 1st numbers differ - expected: '296156367383787', found: '252335286139049'

Test #20:

score: 0
Wrong Answer
time: 39ms
memory: 16752kb

input:

100000 82182
62671 86050
89147 86050
37496 86050
31816 89147
83680 62671
19020 83680
42399 86050
751...

output:

252160116187475

result:

wrong answer 1st numbers differ - expected: '296278552690388', found: '252160116187475'