QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#810119#7216. Boxes on treeLiuxizaiML 0ms0kbC++204.8kb2024-12-11 19:50:312024-12-11 19:50:32

Judging History

你现在查看的是最新测评结果

  • [2024-12-11 19:50:32]
  • 评测
  • 测评结果:ML
  • 用时:0ms
  • 内存:0kb
  • [2024-12-11 19:50:31]
  • 提交

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

result: