QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#354845 | #6560. Broken Minimum Spanning Tree | kevinshan# | TL | 1ms | 3840kb | C++17 | 1.7kb | 2024-03-16 05:09:50 | 2024-03-16 05:09:51 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define all(x) x.begin(), x.end()
#define pb push_back
#define f first
#define s second
const int MX = 2005;
#define FOR(i,a,b) for(int i=a;i<b;i++)
#define For(i,a) FOR(i,0,a)
#define pi pair<int,int>
#define trav(a,b) for(auto& a:b)
vector<pair<pi,int>> adj[MX];
pair<pi,int> adj2[MX];
int n,m;
int findInd(set<int> cmp) {
For(i,n-1) {
int u = adj2[i].f.f;
int v=adj2[i].f.s;
if(cmp.count(u) ^ cmp.count(v)) {
return i;
}
}
assert(false);
return -1;
}
int main()
{
ios_base::sync_with_stdio(0); cin.tie(0);
if (fopen("input.in", "r")) {
freopen("input.in", "r", stdin);
freopen("output.out", "w", stdout);
}
set<int> cmp;
vector<pi> ans;
set<pair<pi,int>> avail;
cin>>n>>m;
For(i,m) {
int u,v,w;cin>>u>>v>>w;
u--;v--;
adj[u].pb({{w,i},v});
adj2[i]={{u,v},w};
}
cmp.insert(0);
trav(x,adj[0]){
avail.insert(x);
}
For(i,n-1) {
while(true) {
auto x = *avail.begin();
int w = x.f.f, ind = x.f.s, v = x.s;
avail.erase(avail.begin());
if(cmp.count(v)) {
continue;
}
if(ind >=n-1) {
ans.pb({findInd(cmp), ind});
}
cmp.insert(v);
trav(x,adj[v]) {
avail.insert(x);
}
break;
}
}
cout << ans.size() << '\n';
trav(x,ans) {
cout << x.f+1 << " " << x.s+1 << '\n';
}
cout << endl;
}
詳細信息
Test #1:
score: 100
Accepted
time: 1ms
memory: 3624kb
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: 0
Accepted
time: 1ms
memory: 3840kb
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:
2 1 7 4 8
result:
ok correct!
Test #3:
score: -100
Time Limit Exceeded
input:
2000 1999 1262 1505 968661582 323 1681 787089412 1132 129 88786681 1909 587 762050278 979 1371 230688681 1686 521 980519364 975 191 887826021 869 461 899130441 1433 259 961154249 1718 547 721696188 1254 1042 458319755 1779 267 85751052 1170 813 283230029 309 20 971682908 224 417 255325364 1084 986 7...