ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#213295 | #3849. 旅行日记 | shiruiheng | 20 | 421ms | 16324kb | C++11 | 1.7kb | 2024-11-10 12:46:20 | 2024-11-10 13:08:25 |
answer
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
//using LL = __int128
#define pi pair<ll, ll>
#define fi first
#define se second
#define N 111111
//#define fi(x) (x->first)
//#define se(x) (x->second)
vector<ll> g[N];
ll n, s, u, v, fa[N], vis[N], sz[N], val[N], sum[N], cnt, ans;
void add(int u, int v){
g[u].push_back(v);
}
bool cmp(int u, int v){
return sz[u] * val[v] > sz[v] * val[u];
}
ll calc(int u, int v){
return sz[v] * val[u] - sz[u] * val[v];
}
void pre(int u, int f){
fa[u] = f;
sz[u] = 1;
val[u] = u;
for(auto v : g[u]){
if(v == f)
continue;
pre(v, u);
sz[u] += sz[v];
val[u] += val[v];
}
}
void dfs(int u, int f){
if(!vis[u]){
ans += u * (++cnt), vis[u] = true;
}
for(auto v : g[u]){
if(v == f)
continue;
dfs(v, u);
}
}
int main(){
mt19937_64 gen(time(0));
scanf("%lld%lld", &n, &s);
for(int i = 1 ; i < n ; i++){
scanf("%lld%lld", &u, &v);
add(u, v);
add(v, u);
}
pre(s, s);
if(sz[1] >= n - 1){
sort(g[1].begin(), g[1].end());
}
else if(n >= 18){
for(int i = 1 ; i <= n ; i++){
for(int j = 0 ; j < g[i].size() ; j++){
for(int k = 1 ; k < g[i].size() ; k++)
if(calc(g[i][k], g[i][k - 1]) <= 0)
swap(g[i][k], g[i][k - 1]);
}
}
}
else{
ll ans1 = 0;
for(int k = 1 ; k <= __lg(20 * n) ; k++){
ans = cnt = 0;
for(int i = 1 ; i <= n ; i++){
shuffle(g[i].begin(), g[i].end(), gen);
sort(g[i].begin(), g[i].end(), cmp);
}
dfs(s, s);
ans1 = max(ans1, ans);
}
printf("%lld", ans1);
return 0;
}
dfs(s, s);
printf("%lld", ans);
return 0;
}
/*
freopen(".in", "r", stdin);
freopen(".out", "w", stdout);
*/
Details
小提示:点击横条可展开更详细的信息
Test #1:
score: 0
Wrong Answer
time: 0ms
memory: 3872kb
input:
10 6 5 8 3 8 9 8 10 3 6 8 7 10 1 7 2 5 4 10
output:
303
result:
wrong answer 1st numbers differ - expected: '304', found: '303'
Test #2:
score: 0
Wrong Answer
time: 0ms
memory: 3864kb
input:
10 7 1 5 10 1 6 5 7 5 4 6 8 6 2 6 3 6 9 1
output:
327
result:
wrong answer 1st numbers differ - expected: '345', found: '327'
Test #3:
score: 0
Wrong Answer
time: 2ms
memory: 3868kb
input:
10 9 4 9 8 9 1 8 6 4 5 1 2 4 10 8 3 6 7 3
output:
313
result:
wrong answer 1st numbers differ - expected: '320', found: '313'
Test #4:
score: 0
Wrong Answer
time: 3ms
memory: 3868kb
input:
10 7 6 1 2 1 8 2 4 6 9 2 10 2 7 6 3 10 5 4
output:
324
result:
wrong answer 1st numbers differ - expected: '336', found: '324'
Test #5:
score: 0
Wrong Answer
time: 0ms
memory: 3864kb
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:
1822
result:
wrong answer 1st numbers differ - expected: '1911', found: '1822'
Test #6:
score: 0
Wrong Answer
time: 0ms
memory: 3872kb
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:
1656
result:
wrong answer 1st numbers differ - expected: '1750', found: '1656'
Test #7:
score: 0
Wrong Answer
time: 0ms
memory: 3864kb
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:
1724
result:
wrong answer 1st numbers differ - expected: '1895', found: '1724'
Test #8:
score: 0
Wrong Answer
time: 0ms
memory: 3872kb
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:
1704
result:
wrong answer 1st numbers differ - expected: '1728', found: '1704'
Test #9:
score: 5
Accepted
time: 45ms
memory: 10852kb
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: 22ms
memory: 10856kb
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: 16ms
memory: 10856kb
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: 12ms
memory: 10856kb
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: 42ms
memory: 16032kb
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: 50ms
memory: 15276kb
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: 36ms
memory: 16324kb
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: 43ms
memory: 13528kb
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: 38ms
memory: 10636kb
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: 38ms
memory: 10676kb
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: 36ms
memory: 10648kb
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: 38ms
memory: 10656kb
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'