QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#253314#7216. Boxes on treeSolitaryDreamWA 1ms5852kbC++173.5kb2023-11-16 21:14:272023-11-16 21:14:27

Judging History

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

  • [2023-11-16 21:14:27]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:5852kb
  • [2023-11-16 21:14:27]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
const int N = 505;
const int M = N * N;
namespace DMST {
    const int inf = 1e9;
    int n, size, pre[N], id[N], vis[N], in[N], ROOT;
    int tag[N];
    struct Edge {
        int u, v, cost;
    } E[M];
    void add(int x, int y, int z) { 
        E[size++] = {x, y, z}; 
    }
    int dmst(int root) {
        int u, v, cnt, ret = 0;
        while (1) {
            for (int i = 0; i < n; ++i) in[i] = inf;
            for (int i = 0; i < size; ++i) {
                u = E[i].u, v = E[i].v;
                if (E[i].cost < in[v] && u != v) {
                    pre[v] = u, in[v] = E[i].cost;
                    if (u == root) ROOT = i;
                }
            }
            for (int i = 0; i < n; ++i) if (i != root && in[i] == inf) return -1;
            cnt = in[root] = 0;
            for (int i = 0; i < n; ++i) id[i] = vis[i] = -1;
            for (int i = 0; i < n; ++i) {
                ret += in[i], v = i;
                while (vis[v] != i && id[v] == -1 && v != root) vis[v] = i, v = pre[v];
                if (v != root && id[v] == -1) {
                    for (u = pre[v]; u != v; u = pre[u]) id[u] = cnt;
                    id[v] = cnt++;
                }
            }
            if (!cnt) break;
            for (int i = 0; i < n; ++i) if (id[i] == -1) id[i] = cnt++;
            for (int i = 0; v = E[i].v, i < size; ++i) {
                E[i].u = id[E[i].u], E[i].v = id[E[i].v];
                if (E[i].u != E[i].v) E[i].cost -= in[v];
            }
            n = cnt, root = id[root];
        }
        return ret;
    }
    // void variable(int &cost, int &root) {
    //     for (int i = )
    // }
}
int n, p[N], ff[N], de[N], m, vis[N], bel[N];
vector<int> cir[N];
vector<int> g[N];
void Dfs(int x, int fa) {
    ff[x] = fa; de[x] = de[fa] + 1;
    for (auto y : g[x]) if (y != fa) Dfs(y, x);
}
int lca[N][N];
int Lca(int x, int y) {
    if (x == y) return x;
    if (de[x] < de[y]) swap(x, y);
    if (lca[x][y]) return lca[x][y];
    return lca[x][y] = Lca(ff[x], y);
}
int Dis(int x, int y) {
    return de[x] + de[y] - 2 * de[Lca(x, y)];
}
vector<int> Get(int x, int y) {
    vector<int> a;
    while (x != y) {
        if (de[x] < de[y]) swap(x, y);
        a.push_back(x);
        x = ff[x];
    }
    a.push_back(x);
    return a;
}
typedef pair<int, int> pii;
inline void Adde(int x, int y, int z) {
    if (x == y) return;
    static set<pii> st;
    if (st.count(pii(x, y))) return;
    st.insert(pii(x, y));
    DMST::add(x, y, z);
}
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> n;
    for (int i = 1; i <= n; ++i) cin >> p[i];
    for (int i = 1, x, y; i < n; ++i) {
        cin >> x >> y;
        g[x].push_back(y);
        g[y].push_back(x);
    }
    Dfs(1, 0);
    int ans = 0;
    for (int i = 1; i <= n; ++i) ans += Dis(i, p[i]);
    for (int i = 1; i <= n; ++i) if (!vis[i]) {
        cir[m].push_back(i);
        vis[i] = 1;
        bel[i] = m;
        for (int x = p[i]; x != i; x = p[x]) {
            vis[x] = 1;
            bel[x] = m;
            cir[m].push_back(x);
        }
        ++m;
    }
    DMST::n = m;
    for (int i = 1; i <= n; ++i) {
        vector<int> pt = Get(i, p[i]);
        for (auto x : pt) Adde(bel[i], bel[x], 0);
    }
    for (int i = 1; i <= n; ++i)
        for (auto j : g[i])
            Adde(bel[i], bel[j], 2);
    ans += DMST::dmst(0);
    cout << ans << endl;
    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 1ms
memory: 5556kb

input:

3
1 3 2
1 2
2 3

output:

4

result:

ok 1 number(s): "4"

Test #2:

score: 0
Accepted
time: 0ms
memory: 3656kb

input:

4
2 1 4 3
1 3
3 2
3 4

output:

6

result:

ok 1 number(s): "6"

Test #3:

score: 0
Accepted
time: 1ms
memory: 5852kb

input:

1
1

output:

0

result:

ok 1 number(s): "0"

Test #4:

score: -100
Wrong Answer
time: 0ms
memory: 3672kb

input:

10
1 6 3 4 5 2 7 8 9 10
10 8
8 6
2 1
6 5
7 6
3 4
5 1
8 9
4 8

output:

20

result:

wrong answer 1st numbers differ - expected: '8', found: '20'