QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#212619 | #5418. Color the Tree | haze | WA | 160ms | 3928kb | C++20 | 4.1kb | 2023-10-13 18:20:56 | 2023-10-13 18:20:56 |
Judging History
answer
#include<bits/stdc++.h>
#define irep(i,l,r) for(int i = l; i <= r; ++i)
#define drep(i,r,l) for(int i = r; i >= l; --i)
#define ceil(pp,qq) (((pp)>0)^((qq)>0)?-Abs(pp)/Abs(qq):(pp)%(qq)?(pp)/(qq)+1:(pp)/(qq))
#define floor(pp,qq) (((pp)>0)^((qq)>0)?-ceil(Abs(pp),Abs(qq)):(pp)/(qq))
#define ll long long
#define LL __int128
using namespace std;
ll Abs(ll x){return x > 0 ? x : - x;}
inline ll read(){
char ch = getchar();
ll s = 0; bool w = 0;
while(!isdigit(ch)){if(ch == '-')w = 1;ch = getchar();}
while(isdigit(ch))s = (s << 3) + (s << 1) + (ch ^ 48), ch = getchar();
return w ? - s : s;
}
const int itinf = 1e9;
const ll llinf = 4e18;
const int mod = 1000000007;
const int N = 500009;
inline int mul(int nma, int nmb){
return ((1ll * nma * nmb % mod) + mod) % mod;
}
void solve(){
int n = read(), lst = 0;
ll ans = 0;
vector<ll>c(n), dp(n), dfn(n);
vector<vector<int>>g(n), dset(n);
vector<array<int, 24>>fa(n), minc(n);
irep(i,0,n - 1)c[i] = minc[i][0] = read();
irep(i,1,n - 1){
int u = read() - 1, v = read() - 1;
g[u].push_back(v);
g[v].push_back(u);
}
auto dfs = [&](auto self, int x) -> void{
// cerr << x << ' ' << endl;
dfn[x] = lst ++;
dset[dp[x]].push_back(x);
for(int y : g[x]){
if(y != 0 && dp[y] == 0){
dp[y] = dp[x] + 1;
fa[y][0] = x;
self(self, y);
}
}
};
dfs(dfs, 0);
// cerr << fa[3][0];
for(int r = 1; r <= 23; ++ r){
for(int i = 0; i < n; ++ i){
fa[i][r] = fa[fa[i][r - 1]][r - 1];
if((i + (1 << (r - 1))) > n)minc[i][r] = minc[i][r - 1];
else minc[i][r] = min(minc[i][r - 1], minc[i + (1 << (r - 1))][r - 1]);
}
}
auto rmq = [&](int l, int r) -> int{
if(l > r)swap(l, r);
int len = r - l + 1, pw = __lg(len);
return min(minc[l][pw], minc[r - (1 << pw) + 1][pw]);
};
auto lca = [&](int x, int y) -> int{
if(x == y)return x;
if(dp[x] < dp[y])swap(x, y);
for(int r = 23; r >= 0; -- r){
if(dp[fa[x][r]] >= dp[y])x = fa[x][r];
}
if(x == y)return x;
for(int r = 23; r >= 0; -- r){
if(fa[x][r] != fa[y][r]){
x = fa[x][r] , y = fa[y][r];
}
}
return fa[x][0];
};
for(int i = 1; i < n; ++ i){
if(dset[i].size()){
dset[i].push_back(0);
sort(dset[i].begin(), dset[i].end(), [&](int x,int y){return dfn[x] < dfn[y];});
}
else break;
int sz = dset[i].size();
for(int j = 0; j + 1 < sz; ++ j){
dset[i].push_back(lca(dset[i][j], dset[i][j + 1]));
}
sort(dset[i].begin(), dset[i].end(), [&](int x,int y){return dfn[x] < dfn[y];});
dset[i].erase(unique(dset[i].begin(), dset[i].end()), dset[i].end());
// cerr << "PRINT dset\n";
// for(int hh : dset[i])cerr << hh << ' ';
// cerr << endl;
vector<array<int, 2>>edge;
vector<vector<int>>tree;
sz = dset[i].size();
map<int,int> idx, fd;
for(int j = 0; j + 1 < sz; ++ j){
int lc = lca(dset[i][j], dset[i][j + 1]);
edge.push_back({lc, dset[i][j + 1]});
if(idx.find(lc) == idx.end())
idx[lc] = idx.size(), fd[idx[lc]] = dp[lc];
if(idx.find(dset[i][j + 1]) == idx.end())
idx[dset[i][j + 1]] = idx.size(),
fd[idx[dset[i][j + 1]]] = dp[dset[i][j + 1]];
}
tree.resize(idx.size());
for(auto [x, y] : edge){
int u = idx[x], v = idx[y];
tree[u].push_back(v);
tree[v].push_back(u);
// cerr << u << ' ' << v << endl;
}
// cerr << endl;
vector<ll>f(idx.size(), llinf);
auto work = [&](auto self, int x, int fax) -> void{
/*
i -> depth
cost = a[depth - dp[u]] or sum f[v]
i - (fd[u])
i - (fd[fax] + 1)
*/
f[x] = rmq(i - fd[fax] - 1, i - fd[x]);
if(i == fd[x]){
// f[x] = c[i - fd[x]];
return;
}
ll alt = 0;
for(int y : tree[x]){
if(fd[y] > fd[x]){
self(self, y, x);
alt += f[y];
}
}
// cout << "Dt " << i - fd[x] << ' ' << f[x] << ' ' << alt << endl;;
f[x] = min(f[x], alt);
};
work(work, 0, 0);
ans += f[0];
// cout << "F= " << f[0] << endl;
// cout << endl;
}
//cout << endl;
printf("%lld\n", ans + c[0]);
}
int main(){
int T = read();
while(T --){
solve();
}
return 0;
}
詳細信息
Test #1:
score: 100
Accepted
time: 0ms
memory: 3860kb
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: 160ms
memory: 3928kb
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:
146 113 189 201 148 225 211 115 100 79 155 68 143 108 142 110 196 198 116 168 138 126 78 218 182 245 152 176 88 153 157 205 71 247 212 193 158 170 152 116 96 116 165 163 221 183 155 91 149 59 56 22 115 182 186 122 121 185 50 105 155 136 159 119 205 78 152 219 80 318 145 116 118 147 197 231 107 177 9...
result:
wrong answer 1st numbers differ - expected: '180', found: '146'