oj.uz

Submission #742808

# Submission time Handle Problem Language Result Execution time Memory
742808 2023-05-17T02:04:03 Z victor_gao Toll (APIO13_toll) C++17
16 / 100
 3 ms 5044 KB 
//#pragma GCC optimize("Ofast,unroll-loops,O3")
//#pragma GCC optimize("avx,avx2,sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,fma,tune=native")
#include<bits/stdc++.h>
//#include<bits/extc++.h>
//#pragma pack(1)
#define fast ios::sync_with_stdio(0); cin.tie(0);
#define int long long
#define pii pair<int,int>
#define x first
#define y second
#define N 100015
using namespace std;
//using namespace __gnu_pbds;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
//typedef tree<int, null_type,less_equal<int>, rb_tree_tag,tree_order_statistics_node_update> order_multiset;
//typedef tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update> order_set;
int n,k,m,cost[30],fa[N],sz[N],ans=0;
pii dp[N];
set<pii>g[N];
vector<pair<int,pii> >edge,add;
struct DSU{
    int boss[N],sz[N];
    void init(int n){
        for (int i=1;i<=n;i++){
            boss[i]=i;
            sz[i]=1;
        }
    }
    int find(int x){
        if (boss[x]==x) return x;
        return boss[x]=find(boss[x]);
    }
    void merge(int a,int b){
        int ra=find(a),rb=find(b);
        if (ra==rb) return;
        if (sz[ra]<sz[rb]) swap(ra,rb);
        sz[ra]+=sz[rb];
        boss[rb]=ra;
    }
}d;
void dfs(int p,int lp,int c){
    dp[p]=max(dp[lp],pii(c,p));
    fa[p]=lp;
    for (auto i:g[p]){
        if (i.x!=lp)
            dfs(i.x,p,i.y);
    }
}
void dfs1(int p,int lp){
    for (auto i:g[p]){
        if (i.x!=lp){
            dfs1(i.x,p);
            ans=(ans+sz[i.x]*i.y);
            sz[p]+=sz[i.x];
        }
    }
}
signed main(){
    fast
    cin>>n>>m>>k;
    for (int i=1;i<=m;i++){
        int a,b,c; cin>>a>>b>>c;
        edge.push_back({c,{a,b}});
    }
    sort(edge.begin(),edge.end());
    d.init(n);
    for (auto [c,tmp]:edge){
        auto [a,b]=tmp;
        if (d.find(a)!=d.find(b)){
            d.merge(a,b);
            g[a].insert({b,c});
            g[b].insert({a,c});
        }
    }
    for (int i=1;i<=k;i++){
        int a,b; cin>>a>>b;
        dfs(a,0,0);
        if (dp[b].x==0) continue;
        else {
            int p=dp[b].y;
            g[p].erase(pii(fa[p],dp[b].x));
            g[fa[p]].erase(pii(p,dp[b].x));
            g[a].insert({b,0});
            g[b].insert({a,0});
            cost[i]=dp[b].x;
            add.push_back({cost[i],{a,b}});
        }
    }
    for (int i=1;i<=n;i++)
        g[i].clear();
    d.init(n);
    for (auto [c,tmp]:add){
        auto [a,b]=tmp;
        if (d.find(a)!=d.find(b)){
            d.merge(a,b);
            g[a].insert({b,c});
            g[b].insert({a,c});
        }
    }
    for (auto [c,tmp]:edge){
        auto [a,b]=tmp;
        if (d.find(a)!=d.find(b)){
            d.merge(a,b);
            g[a].insert({b,0});
            g[b].insert({a,0});
        }
    }
    for (int i=1;i<=n;i++)
        cin>>sz[i];
    dfs1(1,0);
    cout<<ans<<'\n';
}
/*
5 5 1
3 5 2
1 2 3
2 3 5
2 4 4
4 3 6
1 3
10 20 30 40 50
*/

Subtask #1
16.0 / 16.0

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

Subtask #2
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Correct 3 ms 4948 KB Output is correct
3 Incorrect 3 ms 5044 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Correct 3 ms 4948 KB Output is correct
3 Incorrect 3 ms 5044 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #4
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Correct 3 ms 4948 KB Output is correct
3 Incorrect 3 ms 5044 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #5
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Correct 3 ms 4948 KB Output is correct
3 Incorrect 3 ms 5044 KB Output isn't correct
4 Halted 0 ms 0 KB -