QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#128255#6560. Broken Minimum Spanning Treeinstallb#WA 1ms3700kbC++142.2kb2023-07-20 19:36:342023-07-20 19:36:35

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-07-20 19:36:35]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:3700kb
  • [2023-07-20 19:36:34]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 8005;

int fa[N],dep[N],fw[N];
int eu[N],ev[N],w[N];
int swp[N];
vector <pair <int,int> > G[N];

void dfs(int u,int f){
    fa[u] = f;
    dep[u] = dep[f] + 1;
    for(auto [v,ew] : G[u]){
        if(v == f) continue;
        dfs(v,u);
        fw[v] = ew;
    }
}

pair <int,int> get_max(int u,int v){
    vector <pair <int,int> > H;
    if(dep[u] < dep[v]) swap(u,v);
    while(dep[u] < dep[v]){
        H.push_back({w[fw[u]],-fw[u]});
        u = fa[u];
    }
    while(u != v){
        H.push_back({w[fw[u]],-fw[u]});
        H.push_back({w[fw[v]],-fw[v]});
        u = fa[u]; v = fa[v];
    }
    sort(H.begin(),H.end());
    return H.back();
}

void solve(){
    int n,m;
    cin >> n >> m;
    for(int u,v,i = 1;i < n;i ++){
        cin >> u >> v >> w[i];
        eu[i] = u; ev[i] = v;
        G[u].push_back({v,i});
        G[v].push_back({u,i});
    }
    for(int i = n;i <= m;i ++){
        int u,v;
        cin >> u >> v >> w[i];
        eu[i] = u; ev[i] = v;
        dfs(1,0);
        auto [ew,id] = get_max(u,v);
        // cout << ew << ' ' << id << endl;
        id = -id;
        if(ew > w[i]){
            int las = id;
            if(las >= n) las = swp[las];
            swp[las] = i;
            swp[i] = las;

            for(int j = 0;j < G[eu[id]].size();j ++){
                if(G[eu[id]][j].first == ev[id]){
                    swap(G[eu[id]][j],G[eu[id]].back());
                }
            }
            for(int j = 0;j < G[ev[id]].size();j ++){
                if(G[ev[id]][j].first == eu[id]){
                    swap(G[ev[id]][j],G[ev[id]].back());
                }
            }
            G[eu[id]].pop_back();
            G[ev[id]].pop_back();

            G[u].push_back({v,i});
            G[v].push_back({u,i});
        }
    }
    vector <pair <int,int> > ans;
    for(int i = 1;i < n;i ++){
        if(swp[i]) ans.push_back({i,swp[i]});
    }
    cout << ans.size() << '\n';
    for(auto [u,v] : ans) cout << u << ' ' << v << '\n';
}

signed main(){
    ios::sync_with_stdio(false);
    solve();
    return 0;
}

詳細信息

Test #1:

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

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: 1ms
memory: 3700kb

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
3 8

result:

wrong answer not a spanning tree after swap 2