QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#175320 | #6560. Broken Minimum Spanning Tree | SolitaryDream# | WA | 0ms | 6224kb | C++17 | 1.5kb | 2023-09-10 17:25:28 | 2023-09-10 17:25:28 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
using pii=pair<int,int>;
const int N=1e5+1e3+7;
int n,m;
int u[N],v[N],w[N],use[N];
vector<pii> g[N];
vector<int> path,t;
void getp(int x,int T,int f)
{
if(x==T)
path=t;
for(auto [v,id]:g[x])
{
if(v==f)
continue;
if(id<n)
t.push_back(id);
getp(v,T,x);
if(id<n)
t.pop_back();
}
}
int main()
{
scanf("%d%d",&n,&m);
vector<int> out;
for(int i=1;i<=m;i++)
{
scanf("%d%d%d",&u[i],&v[i],&w[i]);
if(i>=n)
out.push_back(i);
else
use[i]=1;
}
sort(out.begin(),out.end(),[&](const int &a,const int &b) {
return w[a]<w[b];
});
vector<pair<int,int> >ans;
for(auto x:out)
{
path.clear();
for(int i=1;i<=n;i++)
g[i].clear();
for(int i=1;i<=m;i++)
if(use[i])
{
g[u[i]].push_back({v[i],i});
g[v[i]].push_back({u[i],i});
}
t.clear();
getp(u[x],v[x],0);
int mxw=-1,p=0;
for(auto e:path)
if(w[e]>mxw)
mxw=w[e],p=e;
if(mxw>=w[x])
{
use[p]=0;
use[x]=1;
ans.push_back({p,x});
}
}
printf("%d\n",(int)ans.size());
for(auto [x,y]:ans)
printf("%d %d\n",x,y);
}
詳細信息
Test #1:
score: 100
Accepted
time: 0ms
memory: 6224kb
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: 6188kb
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:
3 1 7 4 8 3 6
result:
FAIL participant's plan is better than jury!