QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#175320#6560. Broken Minimum Spanning TreeSolitaryDream#WA 0ms6224kbC++171.5kb2023-09-10 17:25:282023-09-10 17:25:28

Judging History

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

  • [2023-09-10 17:25:28]
  • 评测
  • 测评结果:WA
  • 用时:0ms
  • 内存:6224kb
  • [2023-09-10 17:25:28]
  • 提交

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!