QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#810119 | #7216. Boxes on tree | Liuxizai | ML | 0ms | 0kb | C++20 | 4.8kb | 2024-12-11 19:50:31 | 2024-12-11 19:50:32 |
answer
#include <bits/stdc++.h>
#define File(name) freopen(#name".in", "r", stdin); freopen(#name".out", "w", stdout);
using namespace std;
using ll = long long;
using ull = unsigned long long;
template<typename T>
inline T read(){
T n = 0; int f = 1; char ch = getchar();
while(!isdigit(ch)){
if(ch == '-') f = -1;
ch = getchar();
}
while(isdigit(ch)){
n = n * 10 + ch - '0';
ch = getchar();
}
return f * n;
}
template<typename T>
void write(T n){
if(n < 0) return putchar('-'), write(-n);
if(n / 10) write(n / 10);
putchar(n % 10 + '0');
}
void input() {}
template<typename Type, typename... Types>
void input(Type &arg, Types &...args){
arg = read<Type>();
input(args...);
}
namespace Main{
const int N = 5005;
int t, n, p[N], fa[N], dep[N], dfn[N], siz[N], dfnCnt, st[13][N], ans;
int bel[N], len[N];
int e[N][N];
bool vis[N];
pair<int, int> mn[N];
vector<int> g[N];
vector<int> vec;
inline int dmin(int u, int v) { return dep[u] < dep[v] ? u : v; }
inline bool in_subt(int u, int r) { return dfn[u] >= dfn[r] && dfn[u] <= dfn[r] + siz[r] - 1; }
void dfs(int u, int f){
dep[u] = dep[f] + 1;
siz[u] = 1;
st[0][dfn[u] = ++dfnCnt] = f;
for(int v: g[u]) if(v != f) dfs(v, u), siz[u] += siz[v];
}
int lca(int u, int v){
if(u == v) return u;
if(dfn[u] > dfn[v]) swap(u, v);
int lg = log2(dfn[v] - dfn[u]);
return dmin(st[lg][dfn[u] + 1], st[lg][dfn[v] - (1 << lg) + 1]);
}
int dis(int u, int v) { return dep[u] + dep[v] - 2 * dep[lca(u, v)]; }
int dis(int u, int s, int t){
if(in_subt(s, u) ^ in_subt(t, u)) return 0;
return min({dis(u, s), dis(u, t), dis(u, lca(s, t))});
}
void merge(int v, int u){
bel[v] = u;
vec.erase(find(vec.begin(), vec.end(), v));
for(int i: vec) e[u][i] = min(e[u][i], e[v][i]);
for(int i: vec) e[i][u] = min(e[i][u], e[i][v]);
}
void Main(){
input(n);
for(int i = 1; i <= n; i++) input(p[i]);
for(int i = 1, u, v; i < n; i++){
input(u, v);
g[u].push_back(v), g[v].push_back(u);
}
dfs(1, 0);
for(int i = 1; i < 13; i++){
for(int j = 1; j + (1 << i) - 1 <= n; j++){
st[i][j] = dmin(st[i - 1][j], st[i - 1][j + (1 << (i - 1))]);
}
}
memset(e, 0x3f, sizeof(e));
for(int i = 1; i <= n; i++){
if(bel[i]) continue;
bel[i] = i, len[i] = 1;
for(int j = p[i]; j != i; j = p[j]) bel[j] = i, len[i]++;
}
vec = {1};
for(int i = 2; i <= n; i++) if(bel[i] == i && len[i] > 1) vec.push_back(i);
for(int i = 1; i <= n; i++){
if(bel[i] != 1 && len[bel[i]] > 1){
for(int j = 1; j <= n; j++){
e[bel[i]][bel[j]] = min(e[bel[i]][bel[j]], 2 * dis(i, j, p[j]));
}
}
}
vis[1] = true;
for(int i: vec) if(i != 1){
mn[i] = {1e9, -1};
for(int j: vec) if(i != j) mn[i] = min(mn[i], make_pair(e[i][j], j));
if(mn[i].second == -1) { puts("-1"); return; }
}
iota(bel + 1, bel + n + 1, 1);
for(int i = 1; i <= n; i++) ans += dis(i, p[i]);
while(true){
for(int i: vec) if(i != 1) vis[i] = false, mn[i].second = bel[mn[i].second];
bool ok = true;
for(int i: vec){
if(i == 1) continue;
vector<int> path;
int p = i;
while(!vis[p]){
vis[p] = true;
path.push_back(p);
p = mn[p].second;
}
auto it = find(path.begin(), path.end(), p);
if(it != path.end()){
ok = false;
int s = *it;
while(it != path.end()){
for(int j: vec) g[j][*it] -= mn[*it].first;
ans += mn[*it].first;
if(*it != s) merge(*it, s);
it++;
}
mn[s] = {1e9, -1};
for(int j: vec) if(j != s) mn[s] = min(mn[s], make_pair(e[s][j], j));
if(mn[s].second == -1) { puts("-1"); return; }
}
}
if(ok){
for(int i: vec) if(i != 1) ans += mn[i].first;
break;
}
}
write(ans), puts("");
return;
}
} // namespace Main
int main(){
#ifdef Liuxizai
freopen("in", "r", stdin);
freopen("out", "w", stdout);
#endif // Liuxizai
Main::Main();
return 0;
}
详细
Test #1:
score: 0
Memory Limit Exceeded
input:
3 1 3 2 1 2 2 3
output:
4