QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#212810 | #5418. Color the Tree | haze | WA | 155ms | 3772kb | C++20 | 4.1kb | 2023-10-13 20:45:19 | 2023-10-13 20:45:19 |
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) -> ll{
swap(l, r);
if(l > r)return llinf;
// 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[x], i - fd[fax] - 1);
if(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: 3672kb
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: 155ms
memory: 3772kb
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:
-6446744073709551448 -8893488147419103074 191 208 -2446744073709551462 -2446744073709551312 -6446744073709551398 139 114 87 182 83 -2446744073709551374 -6446744073709551438 5553255926290448594 -8893488147419103043 221 -6446744073709551452 -2446744073709551319 241 138 126 80 -2446744073709551234 221 ...
result:
wrong answer 1st numbers differ - expected: '180', found: '-6446744073709551448'