QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#212605 | #5418. Color the Tree | haze | WA | 162ms | 3768kb | C++20 | 4.1kb | 2023-10-13 18:07:37 | 2023-10-13 18:07:37 |
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: 1ms
memory: 3740kb
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: 162ms
memory: 3768kb
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 116 191 208 153 225 211 134 100 85 180 82 157 135 172 117 198 198 137 179 138 126 78 218 190 245 156 176 88 159 157 210 71 247 212 195 176 172 174 116 96 116 180 163 221 183 155 133 149 59 56 22 127 183 186 122 155 194 50 105 155 136 161 123 205 87 152 219 80 362 150 116 129 147 197 231 107 177 ...
result:
wrong answer 1st numbers differ - expected: '180', found: '146'