QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#224029 | #5418. Color the Tree | luanmenglei | WA | 25ms | 11608kb | C++17 | 2.8kb | 2023-10-22 23:13:10 | 2023-10-22 23:13:10 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
void debug(const char *msg, ...) {
#ifdef CLESIP
va_list arg;
static char pbString[512];
va_start(arg,msg);
vsprintf(pbString,msg,arg);
cerr << "[DEBUG] " << pbString << "\n";
va_end(arg);
#endif
}
#define PASSED debug("PASSED (%s) LINE #%s", __FUNCTION__, __LINE__)
using i64 = long long;
using i128 = __int128_t;
template <typename T, typename L> void chkmax(T &x, L y) { if (x < y) x = y; }
template <typename T, typename L> void chkmin(T &x, L y) { if (x > y) x = y; }
const int N = 1e5 + 10;
int n, a[N], dfn[N], cnt, len[N], son[N], dep[N], lg2[N], st[18][N];
i64 f[N], g[N];
vector<int> G[N];
void dfs1(int x, int fa) {
len[x] = 1, son[x] = 0;
for (int y : G[x]) if (y != fa) {
dep[y] = dep[x] + 1;
dfs1(y, x);
chkmax(len[x], len[y] + 1);
if (!son[x] || len[son[x]] < len[y])
son[x] = y;
}
}
void init_st() {
for (int i = 0; i < n; i ++)
st[0][i] = a[i];
for (int i = 1; i < 18; i ++)
for (int j = 0; j + (1 << i) - 1 < n; j ++)
st[i][j] = st[i - 1][j], chkmin(st[i][j], st[i - 1][j + (1 << (i - 1))]);
}
i64 query_st(int l, int r) {
if (l > r)
return 1e18;
int k = lg2[r - l + 1];
return min(st[k][l], st[k][r - (1 << k) + 1]);
}
void dfs2(int x, int fa) {
dfn[x] = ++ cnt;
if (son[x])
dfs2(son[x], x);
for (int y : G[x]) if (y != fa && y != son[x])
dfs2(y, x);
}
void dp(int x, int fa) {
for (int y : G[x]) if (y != fa)
dp(y, x);
f[dfn[x]] = a[0], g[dfn[x]] = 0;
for (int y : G[x]) if (y != fa && y != son[x]) {
for (int i = 1; i <= len[y]; i ++) {
if (g[dfn[x] + i] < i) {
chkmin(f[dfn[x] + i], query_st(g[dfn[x] + i] + 1, i));
g[dfn[x] + i] = i;
}
f[dfn[x] + i] += min(f[dfn[y] + i - 1], query_st(g[dfn[y] + i - 1], i - 1));
}
}
}
void solve() {
cin >> n;
cnt = 0;
for (int i = 1; i <= n; i ++) {
G[i].clear();
g[i] = 0, f[i] = 1e18;
}
for (int i = 0; i < n; i ++)
cin >> a[i];
for (int i = 2, x, y; i <= n; i ++) {
cin >> x >> y;
G[x].push_back(y), G[y].push_back(x);
}
dep[1] = 1;
dfs1(1, 0);
dfs2(1, 0);
init_st();
dp(1, 0);
i64 ans = 0;
for (int i = 1; i <= len[1]; i ++) {
ans += min(f[i], query_st(g[i], i - 1));
}
cout << ans << "\n";
}
signed main() {
for (int i = 2; i < N; i ++) {
lg2[i] = lg2[i / 2] + 1;
}
ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
int tt; cin >> tt;
while (tt --)
solve();
return 0;
}
详细
Test #1:
score: 100
Accepted
time: 2ms
memory: 10224kb
input:
3 4 10 15 40 1 1 2 2 3 2 4 5 10 5 1 100 1000 1 2 2 3 2 4 4 5 4 1000 200 10 8 1 2 2 3 3 4
output:
35 17 1218
result:
ok 3 number(s): "35 17 1218"
Test #2:
score: -100
Wrong Answer
time: 25ms
memory: 11608kb
input:
3000 54 43 44 11 49 17 14 7 30 35 12 34 14 15 8 29 47 30 31 39 17 26 23 26 45 34 50 49 13 35 18 29 15 13 44 47 5 22 20 19 46 30 22 26 13 47 46 43 27 48 48 13 14 30 44 1 2 1 3 2 4 3 5 4 6 2 7 4 8 1 9 3 10 1 11 8 12 2 13 9 14 1 15 1 16 15 17 15 18 7 19 1 20 19 21 13 22 10 23 17 24 9 25 9 26 24 27 8 28...
output:
185 170 222 230 156 255 225 126 100 81 155 73 154 134 149 144 228 230 140 191 155 171 78 282 195 286 195 211 119 197 211 252 88 252 239 241 173 180 195 145 109 149 180 188 226 210 182 97 199 59 56 31 115 224 203 172 155 217 53 143 189 174 173 137 233 105 163 273 80 350 156 133 147 159 240 269 147 22...
result:
wrong answer 1st numbers differ - expected: '180', found: '185'