QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#811943 | #277. Beads and wires | Starrykiller | 0 | 15ms | 8280kb | C++23 | 1.5kb | 2024-12-13 09:28:33 | 2024-12-13 09:28:33 |
Judging History
answer
// Homura Akemi a.k.a. Starrykiller (/user/235125)
// I love Madoka Kaname forever!
#include <bits/stdc++.h>
using namespace std;
auto range(auto l, auto r) { return views::iota(l,r); }
auto rev=views::reverse;
_GLIBCXX_ALWAYS_INLINE void chmax(auto &a, auto b) { a=max(a,b); }
_GLIBCXX_ALWAYS_INLINE void chmin(auto &a, auto b) { a=min(a,b); }
constexpr int MAXN=2e5+10, inf=1e9;
vector<pair<int,int>> g[MAXN]; int n;
int f[MAXN][4], tmp[4];
void dfs(int u, int fa) {
f[u][1]=-inf; f[u][2]=-inf;
for (const auto& [v,w]: g[u]) if (v!=fa) {
dfs(v,u);
tmp[0]=0; tmp[1]=tmp[2]=-inf;
chmax(tmp[0],f[u][0]+max(f[v][0],f[v][2]));
chmax(tmp[1],f[u][1]+max(f[v][0],f[v][2]));
chmax(tmp[2],f[u][2]+max(f[v][0],f[v][2]));
chmax(tmp[0],f[u][0]+f[v][1]+w);
chmax(tmp[1],f[u][1]+f[v][1]+w);
chmax(tmp[2],f[u][2]+f[v][1]+w);
// chmax(tmp[3],f[u][3]+max(f[v][0],f[v][2]));
chmax(tmp[1],f[u][0]+max(f[v][0],f[v][2])+w);
chmax(tmp[2],f[u][1]+max(f[v][0],f[v][2])+w);
// chmax(tmp[3],f[u][2]+f[v][0]+w);
copy(tmp,tmp+4,f[u]);
}
// cerr<<u<<' '<<f[u][0]<<' '<<f[u][1]<<' '<<f[u][2]<<'\n';
}
signed main() {
ios::sync_with_stdio(false);
cin.tie(nullptr); cout.tie(nullptr);
cin>>n;
for (int i=1,u,v,w; i<n; ++i) {
cin>>u>>v>>w;
g[u].emplace_back(v,w);
g[v].emplace_back(u,w);
}
int root=3;
dfs(root,0);
cout<<max(f[root][0],f[root][2])<<'\n';
}
詳細信息
Subtask #1:
score: 0
Wrong Answer
Test #1:
score: 13
Accepted
time: 1ms
memory: 5732kb
input:
5 1 2 10 1 3 40 1 4 15 1 5 20
output:
60
result:
ok single line: '60'
Test #2:
score: 13
Accepted
time: 1ms
memory: 5636kb
input:
10 4 10 2 1 2 21 1 3 13 6 7 1 7 9 5 2 4 3 2 5 8 1 6 55 6 8 34
output:
140
result:
ok single line: '140'
Test #3:
score: 13
Accepted
time: 1ms
memory: 5636kb
input:
10 4 10 5 1 10 7 3 10 10 3 9 10 2 3 5 3 8 9 7 10 3 5 8 9 4 6 6
output:
61
result:
ok single line: '61'
Test #4:
score: 13
Accepted
time: 1ms
memory: 5632kb
input:
10 7 10 1 2 7 3 6 7 5 1 9 5 5 7 3 2 3 3 3 4 3 2 9 5 6 8 3
output:
30
result:
ok single line: '30'
Test #5:
score: 13
Accepted
time: 0ms
memory: 5760kb
input:
10 3 10 6 3 7 6 8 9 3 1 5 1 2 10 4 4 10 2 1 8 6 1 10 10 6 9 7
output:
44
result:
ok single line: '44'
Test #6:
score: 0
Wrong Answer
time: 1ms
memory: 5700kb
input:
10 5 6 9 2 3 5 1 10 8 4 5 9 2 7 8 5 7 10 6 9 4 2 8 9 1 7 5
output:
63
result:
wrong answer 1st lines differ - expected: '62', found: '63'
Subtask #2:
score: 0
Wrong Answer
Test #13:
score: 0
Wrong Answer
time: 1ms
memory: 5700kb
input:
100 48 93 4 12 87 1 27 72 10 3 43 2 33 86 2 37 80 8 51 98 4 34 57 3 5 51 7 15 100 9 41 72 4 14 30 10 27 80 7 50 71 7 6 77 6 36 66 1 47 61 2 71 92 7 20 94 7 3 59 1 55 69 7 16 33 5 71 79 6 18 96 4 4 43 3 1 55 4 65 75 10 82 96 2 30 74 9 12 19 6 46 93 1 83 94 9 22 24 1 27 51 9 33 92 4 25 42 10 71 81 8 3...
output:
471
result:
wrong answer 1st lines differ - expected: '441', found: '471'
Subtask #3:
score: 0
Wrong Answer
Test #23:
score: 0
Wrong Answer
time: 2ms
memory: 5888kb
input:
5000 2198 4992 964 2521 2711 961 3408 4585 975 2746 3304 974 2514 3411 972 602 4079 952 1193 3742 996 774 4530 942 2234 3877 905 346 1537 959 886 3841 937 3126 3342 938 211 2423 977 1725 4740 944 2125 4020 961 1235 3070 903 3109 4669 970 3923 4815 972 2525 4784 979 1159 1511 968 1900 3573 960 2087 2...
output:
4143163
result:
wrong answer 1st lines differ - expected: '3848169', found: '4143163'
Subtask #4:
score: 0
Wrong Answer
Test #32:
score: 0
Wrong Answer
time: 15ms
memory: 8280kb
input:
50000 22758 25880 990 917 25140 901 10537 30620 913 10368 14209 993 40077 48077 900 5064 20728 937 39641 39844 906 819 11079 965 12203 41474 993 13965 27792 923 20713 39385 991 4266 46545 938 27293 40442 937 12696 27693 961 10394 24153 998 24393 26653 926 25825 32799 963 33049 38343 946 15252 41731 ...
output:
41679589
result:
wrong answer 1st lines differ - expected: '38479584', found: '41679589'