ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#213299 | #3849. 旅行日记 | 18112606231 | 40 | 320ms | 26948kb | C++11 | 2.6kb | 2024-11-10 12:50:07 | 2024-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'