QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#224002 | #5418. Color the Tree | luanmenglei | WA | 26ms | 12300kb | C++17 | 2.9kb | 2023-10-22 22:53:13 | 2023-10-22 22:53:14 |
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 <= lg2[n]; 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) {
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 ++) {
f[dfn[x] + i] += f[dfn[y] + i - 1];
}
}
// for (int i = 0; i < len[x]; i ++)
// chkmin(f[dfn[x] + i], a[i]);
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;
}
}
}
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 ++) {
if (g[i] < i - 1) {
chkmin(f[i], query_st(g[i] + 1, i - 1));
}
ans += f[i];
}
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: 0ms
memory: 10212kb
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: 26ms
memory: 12300kb
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:
180 134 222 222 156 255 225 126 100 79 139 73 140 127 143 119 228 179 131 171 128 171 78 282 195 286 152 200 119 188 209 213 88 252 207 206 160 179 184 144 109 148 180 169 226 210 182 85 162 59 56 31 115 216 201 144 155 212 53 155 189 134 173 134 216 106 163 255 80 339 156 133 129 156 219 269 148 22...
result:
wrong answer 2nd numbers differ - expected: '168', found: '134'