QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#354847#6560. Broken Minimum Spanning Treekevinshan#TL 1ms3696kbC++171.7kb2024-03-16 05:14:122024-03-16 05:14:12

Judging History

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

  • [2024-03-16 05:14:12]
  • 评测
  • 测评结果:TL
  • 用时:1ms
  • 内存:3696kb
  • [2024-03-16 05:14:12]
  • 提交

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 = 3005;

#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(unordered_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);
    }
    unordered_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: 3696kb

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: 0ms
memory: 3632kb

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...

output:


result: