QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#812122 | #277. Beads and wires | Starrykiller | 0 | 16ms | 10892kb | C++23 | 2.2kb | 2024-12-13 11:41:24 | 2024-12-13 11:41:25 |
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][2][2][2], T[2][2][2];
void dfs(int u, int fa) {
auto S=f[u];
memset(f[u],0xcf,sizeof(f[u]));
// cerr<<f[u][0][0][0]<<'\n';
f[u][0][0][0]=0;
for (const auto& [v,w]: g[u]) if (v!=fa) {
dfs(v,u);
auto G=f[v];
memset(T,0xcf,sizeof(T)); T[0][0][0]=0;
// no arrow
for (auto i: {0,1})
for (auto j: {0,1})
for (auto k: {0,1})
T[i][j][k]=S[i][j][k]+max(G[0][0][0],G[1][0][0]);
// 加入一条 v->u 的链
chmax(T[1][0][1],S[0][0][0]+max(G[0][0][0],G[1][0][0])+w); // 不配对
chmax(T[1][0][0],S[0][1][0]+max(G[0][0][0],G[1][0][0])+w); // 与一条 u->w 的链配对
// 加入一条 u->v 的链
for (auto i: {0,1})
chmax(T[i][1][0],S[i][0][0]+G[0][0][0]+w), // 不配对
chmax(T[i][0][0],S[i][0][1]+G[0][0][0]+w); // 与一条 w->u 的链配对
// 加入一条 u->v 的链,并与 v->w 的链连起来
for (auto i: {0,1})
for (auto j: {0,1})
for (auto k: {0,1})
chmax(T[i][j][k],S[i][j][k]+G[0][1][0]+w);
for (auto i: {0,1})
for (auto j: {0,1})
for (auto k: {0,1})
S[i][j][k]=T[i][j][k];
}
}
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);
}
// if (n>10000) return 0;
int ans=0;
dfs(1,0);
ans=max(f[1][0][0][0],f[1][1][0][0]);
// for (int root=1; root<=n; ++root) {
// // int root=1;
// dfs(root,0);
// chmax(ans,max(f[root][0][0][0],f[root][1][0][0]));
// }
cout<<ans<<'\n';
}
Details
Tip: Click on the bar to expand more detailed information
Subtask #1:
score: 0
Wrong Answer
Test #1:
score: 13
Accepted
time: 1ms
memory: 5604kb
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: 5692kb
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: 0
Wrong Answer
time: 0ms
memory: 5688kb
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:
59
result:
wrong answer 1st lines differ - expected: '61', found: '59'
Subtask #2:
score: 0
Wrong Answer
Test #13:
score: 15
Accepted
time: 1ms
memory: 5760kb
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:
441
result:
ok single line: '441'
Test #14:
score: 0
Wrong Answer
time: 0ms
memory: 5608kb
input:
100 38 97 8 26 29 9 62 73 7 13 62 8 6 63 3 22 82 9 57 90 10 34 40 10 86 87 6 62 72 8 35 67 4 24 47 10 14 60 9 43 92 4 85 91 1 56 62 5 57 69 6 30 45 8 69 92 5 15 99 1 6 78 9 64 89 1 20 88 8 66 92 2 31 63 4 31 70 8 42 79 2 11 59 2 9 97 6 24 62 8 8 21 9 84 100 7 4 50 10 54 63 5 24 98 10 2 97 1 4 25 3 2...
output:
501
result:
wrong answer 1st lines differ - expected: '498', found: '501'
Subtask #3:
score: 0
Wrong Answer
Test #23:
score: 0
Wrong Answer
time: 2ms
memory: 7932kb
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:
3856257
result:
wrong answer 1st lines differ - expected: '3848169', found: '3856257'
Subtask #4:
score: 0
Wrong Answer
Test #32:
score: 0
Wrong Answer
time: 16ms
memory: 10892kb
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:
38571849
result:
wrong answer 1st lines differ - expected: '38479584', found: '38571849'