Submission #207752

#	Time	Username	Problem	Language	Result	Execution time	Memory
207752		shihan04	Beads and wires (APIO14_beads)	C++17	0 / 100	6 ms	504 KiB

beads

#include<bits/stdc++.h>
using namespace std;
int main()
{
    int n,a,b,c,x=0,t=0;
    cin>>n;
    vector <int> node[n+1],N(n+1,0),v;
    map <pair<int,int>,int> m;
    for(int i=0;i<n-1;i++){
        cin>>a>>b>>c;
        node[a].push_back(b);
        node[b].push_back(a);
        N[a]++;
        N[b]++;
        t+=c;
        m.insert(make_pair(make_pair(a,b),c));
        m.insert(make_pair(make_pair(b,a),c));
    }
    for(int i=1;i<=n;i++){
        if(N[i]==1){
            x++;
            v.push_back(m[make_pair(i,node[i][0])]);
        }
    }
    sort(v.begin(),v.end());
    int l=2*x-n-1;
    if(l<0){
        l=1;
    }
    for(int i=0;i<l;i++){
        t-=v[i];
    }
    cout<<t;
    return 0;
}

• Subtask 1: 0 / 13
• Subtask 2: 0 / 15
• Subtask 3: 0 / 29
• Subtask 4: 0 / 43