QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#402656 | #7415. Fast Spanning Tree | 24bot | TL | 4ms | 22916kb | C++14 | 1.6kb | 2024-05-01 09:24:35 | 2024-05-01 09:24:37 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
const int N = 4e5 + 5;
const int INF = 1e9 + 5;
int n, m;
int a[N], fa[N], use[N];
vector<int> ans;
int find(int x) { return fa[x] == x ? x : fa[x] = find(fa[x]); }
struct Edge {
int u, v, c;
} e[N];
priority_queue<int, vector<int>, greater<int>> todo;
#define pii pair<int, int>
priority_queue<pii, vector<pii>, greater<pii>> q[N];
inline void add(int i) {
if (use[i]) return;
int x = find(e[i].u), y = find(e[i].v);
if (x == y) return;
if (a[x] + a[y] >= e[i].c) return todo.push(i), void();
q[x].emplace((e[i].c - a[x] - a[y] + 1) / 2, i);
q[y].emplace((e[i].c - a[y] - a[x] + 1) / 2, i);
}
inline void merge(int i) {
int u = find(e[i].u), v = find(e[i].v);
if (u == v) return; ans.push_back(i); use[i] = 1;
if (q[u].size() > q[v].size()) swap(u, v);
fa[u] = v; a[v] = min(INF, a[u] + a[v]);
while (q[u].size()) {
auto it = q[u].top(); q[u].pop();
if (a[v] >= it.first) add(it.second);
else q[v].push(it);
}
while (q[v].size()) {
auto it = q[v].top(); q[v].pop();
if (a[v] >= it.first) add(it.second);
else { q[v].push(it); break; }
}
}
int main(void) {
ios::sync_with_stdio(0);
cin >> n >> m;
for (int i = 1; i <= n; ++i) cin >> a[i], fa[i] = i;
for (int i = 1; i <= m; ++i) cin >> e[i].u >> e[i].v >> e[i].c, add(i);
while (!todo.empty()) {
int i = todo.top(); todo.pop();
merge(i);
}
cout << ans.size() << "\n";
for (int i : ans) cout << i << " "; cout << "\n";
return 0;
}
详细
Test #1:
score: 100
Accepted
time: 0ms
memory: 20368kb
input:
5 5 1 4 3 4 0 4 5 5 3 1 1 2 5 2 4 3 1 4 1 4
output:
4 2 3 1 4
result:
ok 5 number(s): "4 2 3 1 4"
Test #2:
score: 0
Accepted
time: 0ms
memory: 21820kb
input:
3 5 3 2 2 1 2 6 1 2 6 1 2 3 1 2 6 2 3 6
output:
2 3 5
result:
ok 3 number(s): "2 3 5"
Test #3:
score: 0
Accepted
time: 4ms
memory: 22916kb
input:
10 20 4 6 6 1 7 9 1 8 7 9 5 3 2 1 10 10 5 6 7 9 6 9 3 1 1 6 8 1 5 7 0 9 5 4 10 3 4 8 6 8 3 10 6 5 3 8 3 7 9 1 9 10 10 1 0 5 7 6 6 10 1 6 5 9 5 8 2 9 2 4
output:
8 1 2 3 4 5 6 7 20
result:
ok 9 numbers
Test #4:
score: -100
Time Limit Exceeded
input:
10 20 0 10 4 6 2 0 2 0 2 8 5 10 8 7 1 6 10 5 0 9 8 0 5 8 4 5 1 8 10 3 6 5 4 3 9 2 6 10 3 6 4 3 1 3 10 3 6 1 3 3 2 5 6 9 2 4 2 5 10 6 5 8 6 3 2 1 0 2 3 6