QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#253314 | #7216. Boxes on tree | SolitaryDream | WA | 1ms | 5852kb | C++17 | 3.5kb | 2023-11-16 21:14:27 | 2023-11-16 21:14:27 |
Judging History
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'