Submission #544656

#	Time	Username	Problem	Language	Result	Execution time	Memory
544656		pokmui9909	비용 (KOI11_cost)	C++17	24 / 24	38 ms	6368 KiB

cost

#include <bits/stdc++.h>
using namespace std;
 
using ll = long long;
const ll MOD = 1e9;
 
struct st
{
    ll s, e, c;
};
 
vector<st> E;
 
struct UnionFind
{
    ll p[100005], s[100005];
    UnionFind(){ for(ll i = 0; i < 100005; i++) p[i] = -1, s[i] = 1;}
 
    ll Find(ll n)
    {
        if(p[n] == -1) return n;
        else return p[n] = Find(p[n]);
    }
 
    void Union(ll a, ll b)
    {
        a = Find(a), b = Find(b);
        if(a == b) return;
        p[b] = a;
        s[a] += s[b];
        s[b] = 0;
    }
 
    ll Size(ll n) {return s[Find(n)];}
};
 
int main()
{
    cin.tie(0); cout.tie(0);
    ios_base::sync_with_stdio(false);
 
    ll n, m; cin >> n >> m;
    ll k = 0;
    for(ll i = 0; i < m; i++)
    {
        ll s, e, c; cin >> s >> e >> c;
        E.push_back({s, e, c});
        k += c;
    }
    sort(E.begin(), E.end(), [&](st a, st b) -> bool{return a.c > b.c;});
    UnionFind uf;
    ll ans = 0;
    for(ll i = 0; i < m; i++)
    {
        ll s = E[i].s, e = E[i].e, c = E[i].c;
        if(uf.Find(s) == uf.Find(e)) {k -= c; continue;}
        ans += uf.Size(s) * uf.Size(e) % MOD * k % MOD;
        ans %= MOD;
        k -= c;
        uf.Union(s, e);
    }
    cout << ans;
}

• Subtask 1: 4.8 / 4.8
• Subtask 2: 7.2 / 7.2
• Subtask 3: 12 / 12