QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#165451 | #6560. Broken Minimum Spanning Tree | PhantomThreshold# | WA | 1ms | 3568kb | C++20 | 1.3kb | 2023-09-05 18:17:31 | 2023-09-05 18:17:31 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
int main()
{
ios_base::sync_with_stdio(false);
int n,m;
cin>>n>>m;
vector<tuple<int,int,int,int>> edges;
vector<set<tuple<int,int,int>>> G(n+5);
auto addedge=[&](int u,int v,int w,int id)
{
G[u].emplace(v,w,id);
G[v].emplace(u,w,id);
};
auto deledge=[&](int u,int v,int w,int id)
{
G[u].erase({v,w,id});
G[v].erase({u,w,id});
};
vector<int> in(m+5);
for(int i=1;i<=m;i++)
{
int u,v,w;
cin>>u>>v>>w;
edges.emplace_back(w,u,v,i);
if(i<n)addedge(u,v,w,i),in[i]=1;
}
vector<pair<int,int>> ans;
sort(edges.begin(),edges.end());
vector<int> vis(n+5),maxx(n+5),maxp(n+5);
function<void(int)> dfs=[&](int u)
{
// cerr<<"dfs "<<u<<endl;
vis[u]=1;
for(auto [v,w,id]:G[u])
{
if(not vis[v])
{
if(maxx[u]<w)maxx[v]=w,maxp[v]=id;
else maxx[v]=maxx[u],maxp[v]=maxp[u];
dfs(v);
}
}
};
for(auto [w,u,v,id]:edges)
{
if(in[id])continue;
fill(vis.begin(),vis.end(),0);
dfs(u);
// cerr<<w<<' '<<maxx[v]<<endl;
if(maxx[v]>w)
{
ans.emplace_back(maxp[v],id);
for(auto [ww,uu,vv,ii]:edges)
{
if(ii==maxp[v])
deledge(uu,vv,ww,ii);
}
addedge(u,v,w,id);
}
}
cout<<ans.size()<<endl;
for(auto [x,y]:ans)
cout<<x<<' '<<y<<endl;
return 0;
}
詳細信息
Test #1:
score: 100
Accepted
time: 1ms
memory: 3496kb
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: 0ms
memory: 3568kb
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 1 8
result:
wrong answer bad swap 1 8