QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#811935 | #277. Beads and wires | Starrykiller | 0 | 16ms | 9316kb | C++23 | 1.3kb | 2024-12-13 09:18:54 | 2024-12-13 09:18:57 |
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;
vector<pair<int,int>> g[MAXN]; int n;
int f[MAXN][4], tmp[4];
void dfs(int u, int fa) {
for (const auto& [v,w]: g[u]) if (v!=fa) {
dfs(v,u);
fill(tmp,tmp+4,0);
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[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][1],f[v][3])+w);
chmax(tmp[3],f[u][0]+max(f[v][0],f[v][2])+w);
copy(tmp,tmp+4,f[u]);
}
}
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: 5620kb
input:
5 1 2 10 1 3 40 1 4 15 1 5 20
output:
60
result:
ok single line: '60'
Test #2:
score: 0
Wrong Answer
time: 1ms
memory: 5688kb
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:
128
result:
wrong answer 1st lines differ - expected: '140', found: '128'
Subtask #2:
score: 0
Wrong Answer
Test #13:
score: 0
Wrong Answer
time: 1ms
memory: 5704kb
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:
394
result:
wrong answer 1st lines differ - expected: '441', found: '394'
Subtask #3:
score: 0
Wrong Answer
Test #23:
score: 0
Wrong Answer
time: 0ms
memory: 5932kb
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:
3432224
result:
wrong answer 1st lines differ - expected: '3848169', found: '3432224'
Subtask #4:
score: 0
Wrong Answer
Test #32:
score: 0
Wrong Answer
time: 16ms
memory: 9316kb
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:
34185277
result:
wrong answer 1st lines differ - expected: '38479584', found: '34185277'