QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#240976#6560. Broken Minimum Spanning TreeMovingUp#WA 0ms3628kbC++142.7kb2023-11-05 21:32:512023-11-05 21:32:52

Judging History

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

  • [2023-11-05 21:32:52]
  • 评测
  • 测评结果:WA
  • 用时:0ms
  • 内存:3628kb
  • [2023-11-05 21:32:51]
  • 提交

answer

#include <bits/stdc++.h>

using namespace std;

struct edge {
  int id;
  int u, v, w;

  bool operator<(const edge &o) const { return w < o.w; }
};

struct dsu {
  vector<int> parent, subtree;

  void init(int n) {
    parent.resize(n);
    subtree.resize(n);

    for (int i = 0; i < n; i++) {
      subtree[i] = 1;
      parent[i] = i;
    }
  }

  int findParent(int x) {
    if (parent[x] == x)
      return x;
    else {
      parent[x] = findParent(parent[x]);
      return parent[x];
    }
  }

  void unite(int parX, int parY) {
    if (subtree[parX] < subtree[parY]) {
      parent[parX] = parY;
      subtree[parY] += subtree[parX];
    } else {
      parent[parY] = parX;
      subtree[parX] += subtree[parY];
    }
  }
};

int64_t findMst(int n, const vector<edge> &edges, int edgeId) {
  dsu d;
  d.init(n);

  int64_t ans = 0;
  for (auto e : edges) {
    if (e.id == edgeId) {
      ans += e.w;
      d.unite(e.u, e.v);
    }
  }

  for (auto e : edges) {
    if (e.id == edgeId) {
      continue;
    }

    int parX = d.findParent(e.u);
    int parY = d.findParent(e.v);

    if (parX != parY) {
      ans += e.w;
      d.unite(parX, parY);
    }
  }

  return ans;
}

int findReplacement(int n, const vector<edge> &edges, vector<bool>& forced) {
  dsu d;
  d.init(n);

  for (auto e : edges) {
    if (forced[e.id]) {
      d.unite(e.u, e.v);
    }
  }

  for (auto e : edges) {
    if (forced[e.id]) {
      continue;
    }

    int parX = d.findParent(e.u);
    int parY = d.findParent(e.v);

    if (parX != parY) {
	  return e.id;
    }
  }

  assert(false);
}

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);

  int n, m;
  cin >> n >> m;

  vector<edge> edges(m);
  for (int i = 0; i < m; i++) {
    int u, v, w;
    cin >> u >> v >> w;

    u--;
    v--;

    edges[i] = {i, u, v, w};
  }

  sort(edges.begin(), edges.end());

  int64_t globalMst = findMst(n, edges, -1);

  vector<bool> keep(n - 1, false);
  for (int i = 0; i < n - 1; i++) {
    int64_t currMst = findMst(n, edges, i);

    if (currMst == globalMst) {
      keep[i] = true;
    }
  }

  dsu d;
  d.init(n);

  vector<bool> forced(m);
  vector<int> removals;
  for (int i = 0; i < n - 1; i++) {
	forced[i] = true;
	if (!keep[i]) {
		removals.push_back(i);
	}
  }

  vector<pair<int, int>> changes;
  while (!removals.empty()) {
	int id = removals.back();
	removals.pop_back();

	forced[id] = false;
	int replacement = findReplacement(n, edges, forced);
	forced[replacement] = true;
	changes.push_back({id, replacement});
  }

  cout << changes.size() << endl;
  for (auto [x, y] : changes) {
    cout << x + 1 << " " << y + 1 << endl;
  }
}

詳細信息

Test #1:

score: 100
Accepted
time: 0ms
memory: 3616kb

input:

4 4
1 2 10
2 3 3
3 4 1
1 4 4

output:

1
1 4

result:

ok correct!

Test #2:

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

input:

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

output:

0

result:

FAIL participant's MST is better than jury!