Submission #745095

#	Time	Username	Problem	Language	Result	Execution time	Memory
745095		zeta7532	Beads and wires (APIO14_beads)	C++17	0 / 100	1 ms	296 KiB

beads

#include <bits/stdc++.h>
#pragma GCC target("avx2")
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
using namespace std;
using ll = long long;
const ll mod = 998244353;
#define fi first
#define se second
#define rep(i,n) for(ll i=0;i<n;i++)
#define all(x) x.begin(),x.end()
#define faster ios::sync_with_stdio(false);cin.tie(nullptr)

struct unionfind{
    unionfind() {}
    vector<ll> par,sz;
    unionfind(ll N):par(N),sz(N){
        rep(i,N) par[i]=i,sz[i]=1;
    }
    ll root(ll x){
        if(par[x]==x) return x;
        ll t=root(par[x]);
        par[x]=t;
        return t;
    }
    void unite(ll x,ll y){
        ll rx=root(x);
        ll ry=root(y);
        if(rx==ry) return;
        if(sz[rx]>sz[ry]) swap(rx,ry);
        par[rx]=ry;
        sz[ry]+=sz[rx];
    }
    bool same(ll x,ll y){
        ll rx=root(x);
        ll ry=root(y);
        return rx==ry;
    }
    ll size(ll x){
        return sz[x];
    }
};

int main() {
    ll N;
    cin >> N;
    vector<ll> A(N-1),B(N-1),C(N-1);
    ll sum=0;
    vector<pair<ll,ll>> V;
    vector<ll> deg(N,0);
    rep(i,N-1){
        cin >> A[i] >> B[i] >> C[i];
        A[i]--,B[i]--;
        deg[A[i]]++;
        deg[B[i]]++;
        sum+=C[i];
        V.push_back({C[i],i});
    }
    sort(all(V));
    reverse(all(V));
    vector<ll> cnt(N,0);
    vector<bool> edge(N-1,true);
    ll sum1=0;
    ll sum2=0;
    rep(i,N-1){
        ll j=V[i].se;
        if(deg[A[j]]>1&&deg[B[j]]>1){
            
        }else{
            if(deg[A[j]]==1){
                if(cnt[B[j]]==2){
                    edge[j]=false;
                    sum1+=C[j];
                    sum2++;
                }else{
                    cnt[B[j]]++;
                }
            }
            if(deg[B[j]]==1){
                if(cnt[A[j]]==2){
                    edge[j]=false;
                    sum1+=C[j];
                    sum2++;
                }else{
                    cnt[A[j]]++;
                }
            }
        }
    }
    if((N-1-sum2)%2==0){
        cout << sum-sum1 << endl;
        return 0;
    }
    ll sum3=1e9;
    rep(i,N-1){
        if(edge[i]==false) continue;
        edge[i]=false;
        unionfind tree(N);
        rep(j,N-1){
            if(edge[j]) tree.unite(A[j],B[j]);
        }
        if(tree.size(tree.root(A[i]))%2==1) sum3=min(sum3,C[i]);
        edge[i]=true;
    }
    cout << sum-sum1-sum3 << endl;
    return 0;
}

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