oj.uz

Submission #544656

# Submission time Handle Problem Language Result Execution time Memory
544656 2022-04-02T14:15:45 Z pokmui9909 비용 (KOI11_cost) C++17
24 / 24
 38 ms 6368 KB 
#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

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1876 KB Output is correct
2 Correct 1 ms 1876 KB Output is correct
3 Correct 1 ms 1876 KB Output is correct
4 Correct 1 ms 1884 KB Output is correct

Subtask #2
7.2 / 7.2

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1832 KB Output is correct
2 Correct 2 ms 1876 KB Output is correct
3 Correct 2 ms 1896 KB Output is correct
4 Correct 2 ms 2004 KB Output is correct
5 Correct 3 ms 2196 KB Output is correct
6 Correct 4 ms 2472 KB Output is correct

Subtask #3
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 3048 KB Output is correct
2 Correct 17 ms 4272 KB Output is correct
3 Correct 33 ms 6128 KB Output is correct
4 Correct 8 ms 3024 KB Output is correct
5 Correct 35 ms 6336 KB Output is correct
6 Correct 17 ms 4324 KB Output is correct
7 Correct 38 ms 6332 KB Output is correct
8 Correct 34 ms 6248 KB Output is correct
9 Correct 35 ms 6368 KB Output is correct
10 Correct 36 ms 6344 KB Output is correct