QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#129458 | #5418. Color the Tree | Alinxester | RE | 2ms | 24212kb | C++14 | 4.0kb | 2023-07-22 19:48:09 | 2023-07-22 19:50:31 |
Judging History
answer
#include<bits/stdc++.h>
#define int long long
#define ll long long
#define mod 998244353
#define int128 __int128
#define base 23333
#define base2 19260817
#define db double
#define ldb long double
#define eps 1e-8
#define cmpeps 1e-18
#define lowbit(x) (x & -x)
#define un unsigned
#define rep(i,x,y) for (int i = (x); i <= (y); ++i)
#define drep(i,x,y) for (int i = (x); i >= (y); --i)
#define go(i,u) for (int i = head[u]; i; i = edge[i].next)
#define go_(i,u) for (int i = head[u]; ~i; i = edge[i].next)
#define pii pair<int, int>
#define MP make_pair
#define fir first
#define sec second
//#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<20,stdin),p1==p2)?EOF:*p1++)
using namespace std;
//char buf[1<<21],*p1=buf,*p2=buf;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
template<typename T> inline T rnd(T l,T r) {return uniform_int_distribution<T>(l , r)(rng);}
template<typename T> inline void read (T &t) {
t = 0; char f = 0, ch = getchar(); ldb d = 0.1;
while (ch > '9' || ch < '0') f |= (ch == '-'), ch = getchar();
while (ch <= '9' && ch >= '0') t = t * 10 + ch - 48, ch = getchar();
if (ch == '.') {
ch = getchar();
while (ch <= '9' && ch >= '0') t += d * (ch ^ 48), d *= 0.1, ch = getchar();
}
t = (f ? -t : t);
}
template <typename T, typename... Args>
inline void read (T& t, Args&... args) { read(t); read(args...); }
inline void write (int x) {
if (x >= 10) write(x / 10);
cout << (ll) (x % 10);
}
const int N = 2e5 + 2, INF = 1e18 + 2;
int n, a[N], head[N], pos;
int ans;
struct Seg_tree {
int tree[N << 2];
inline void pushup (int rt) {
tree[rt] = min(tree[rt << 1], tree[rt << 1 | 1]); }
inline void build (int rt, int l, int r) {
if (l == r) {
tree[rt] = a[l];
return;
}
int mid = (l + r) >> 1;
build(rt << 1, l, mid), build(rt << 1 | 1, mid + 1, r);
pushup(rt);
}
inline int query (int rt, int l, int r, int L, int R) {
if (L <= l && r <= R) return tree[rt];
int mid = (l + r) >> 1, ret = INF;
if (L <= mid) ret = min(ret, query(rt << 1, l, mid, L, R));
if (R > mid) ret = min(ret, query(rt << 1 | 1, mid + 1, r, L, R));
return ret;
}
}seg_tree;
struct Edge { int to, next; }edge[N << 1];
inline void add_edge (int u, int v) {
edge[++pos] = (Edge) {v, head[u]}, head[u] = pos; }
int dfn[N], dfc, dep[N], son[N], mxdep[N], fath[N], top[N];
vector<pii > f[N];
inline void merge (int u, int v) {
int size1 = (int)f[u].size(), size2 = (int)f[v].size();
rep (i, 0, size2 - 1) {
int d = size2 - i + dep[v] - 1, p = size1 + dep[u] - d - 1;
f[u][p].fir = min(f[u][p].fir, seg_tree.query(1, 0, n - 1, d - f[u][p].sec, d - dep[u])) + min(f[v][p].fir, seg_tree.query(1, 0, n - 1, d - f[v][p].sec, d - dep[v]));
f[u][p].sec = dep[u];
}
}
inline void dfs1 (int u, int fa) {
dep[u] = dep[fa] + 1, fath[u] = fa;
go (i, u) {
int v = edge[i].to;
if (v == fa) continue;
dfs1(v, u);
if (dep[v] > mxdep[u]) son[u] = v, mxdep[u] = dep[v];
}
}
inline void dfs2 (int u, int Top) {
dfn[u] = ++dfc, top[u] = Top;
go (i, u) {
int v = edge[i].to;
if (v == fath[u]) continue;
if (son[u] == v) dfs2(v, Top);
else dfs2(v, v);
}
if (!son[u]) f[u].emplace_back(MP(a[0], dep[u]));
else {
swap(f[u], f[son[u]]), f[son[u]].clear();
f[u].emplace_back(MP(a[0], dep[u]));
go (i, u) {
int v = edge[i].to;
if (v == fath[u] || v == son[u]) continue;
merge(u, v), f[v].clear();
}
}
}
int T;
signed main() {
read(T);
while (T--) {
memset(head, 0, sizeof head), memset(mxdep, 0, sizeof mxdep), memset(son, 0, sizeof son);
ans = pos = dfc = 0;
read(n);
rep (i, 0, n - 1) read(a[i]);
seg_tree.build(1, 0, n - 1);
int u, v;
rep (i, 1, n - 1) read(u, v), add_edge(u, v), add_edge(v, u);
dfs1(1, 0), dfs2(1, 1);
rep (i, 0, (int) f[1].size() - 1) {
int d = (int) f[1].size() - i;
ans += min(f[1][i].fir, seg_tree.query(1, 0, n - 1, d - f[1][i].sec, d - 1));
}
printf("%lld\n", ans);
}
return 0;
}
/*
1
4
10 15 40 1
1 2
2 3
2 4
*/
详细
Test #1:
score: 100
Accepted
time: 2ms
memory: 24212kb
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
Dangerous Syscalls
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...