QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#152712#6560. Broken Minimum Spanning TreeBUET_POISSON#RE 1ms3612kbC++202.7kb2023-08-28 18:16:582023-08-28 18:16:59

Judging History

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

  • [2023-08-28 18:16:59]
  • 评测
  • 测评结果:RE
  • 用时:1ms
  • 内存:3612kb
  • [2023-08-28 18:16:58]
  • 提交

answer

#include <bits/stdc++.h>
 
using namespace std;
#define getbit(n, i) (((n) & (1LL << (i))) != 0) 
#define setbit0(n, i) ((n) & (~(1LL << (i)))) 
#define setbit1(n, i) ((n) | (1LL << (i))) 
#define togglebit(n, i) ((n) ^ (1LL << (i))) 
#define lastone(n) ((n) & (-(n))) 
char gap = 32;
#define int long long
#define ii pair<int, int>

#define ll long long 
#define lll __int128_t
#define pb push_back

set<pair<int, int>> adj[2001];

int parent[2001];
int parent_wt[2001];
void recalc(int root, int par, int wt) {
    parent[root] = par;
    parent_wt[root] = wt;
    for(auto x: adj[root]) {
        if(x.first == par) continue;
        recalc(x.first, root, x.second);
    }
}

void add_edge(int x, int y, int w) {
    adj[x].insert({y, w});
    adj[y].insert({x, w});
}

void remove_edge(int x, int y, int w) {
    adj[x].erase({y, w});
    adj[y].erase({x, w});
}
vector<pair<int, int>> extra_edge;
map<pair<pair<int, int>, int>, int> id;
int find_black_sheep(int x, int y, int w) {
    recalc(x, 0, 0);
    int curr = y;
    int max_val = 0;
    int max_id = -1;
    while(curr != x) {
        int idx = id[{{curr, parent[curr]}, parent_wt[curr]}];
        if(max_val < parent_wt[curr]) max_val = parent_wt[curr], max_id = idx;
        curr = parent[curr];
    }
    if(max_val <= w) return -1;

    return max_id;
}
void solve() {
    int n, m; cin >> n >> m;
    vector<pair<pair<int, int>, int>> edges;
    
    for(int i = 1; i <= m; i++) {
        int u, v, w; cin >> u >> v >> w;
        if(i <= n - 1) {
            add_edge(u, v, w);
        }
        edges.push_back({{u, v}, w});
        id[{{u, v}, w}] = i - 1;
    }

    for(int i = n - 1; i < m; i++) {
        extra_edge.push_back({edges[i].second, i});
    }
     if(extra_edge.size() >= 2)
        sort(extra_edge.begin(), extra_edge.end());
    int ans = 0;
    vector<pair<int, int>> res;
    for(int i = 0; i < extra_edge.size(); i++) {
        int idx = extra_edge[i].second;
        idx = find_black_sheep(edges[idx].first.first, edges[idx].first.second, edges[idx].second);
        if(idx == -1) {
            continue;
        }
        int rem = idx + 1;
        ans++;
        remove_edge(edges[idx].first.first, edges[idx].first.second, edges[idx].second);
        idx = extra_edge[i].second;
        int ad = idx + 1;
        res.push_back({rem, ad});
        add_edge(edges[idx].first.first, edges[idx].first.second, edges[idx].second);
    }

    cout << ans << "\n";
    for(auto x: res) cout << x.first << " " << x.second << "\n";
}
signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    solve();
}

詳細信息

Test #1:

score: 100
Accepted
time: 1ms
memory: 3612kb

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
Runtime Error

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:


result: