Submission #768786

#	Time	Username	Problem	Language	Result	Execution time	Memory
768786		1075508020060209tc	Janjetina (COCI21_janjetina)	C++14	0 / 110	1 ms	212 KiB

Main

#include<bits/stdc++.h>
using namespace std;
//#define int long long
#define X first
#define Y second
int n;int K;
int uf[200005];
int usz[200005];
pair<int,pair<int,int>>e[200005];
int fin(int x){
if(uf[x]==x){return x;}
uf[x]=fin(uf[x]);
return uf[x];
}
void mrg(int a,int b){
int pa=fin(a);int pb=fin(b);
uf[pa]=pb;
usz[pb]+=usz[pa];
}

signed main(){
cin>>n>>K;
for(int i=1;i<=n-1;i++){
    cin>>e[i].second.first>>e[i].second.second>>e[i].first;
}
sort(e+1,e+n-1+1);
for(int i=1;i<=n;i++){
    uf[i]=i;
    usz[i]=1;
}
long long ans=0;
for(int i=1;i<=n-1;i++){
    int W=e[i].first;
    //L<=W-K
    int a=e[i].second.first;int b=e[i].second.second;
    a=fin(a);b=fin(b);
    if(usz[a]>usz[b]){
        swap(a,b);
    }
    for(int j=1;j<=usz[a];j++){
        ans+=min((W-K)-j+1,usz[b]);
    }
    mrg(a,b);
}
cout<<ans*2<<endl;

}

• Subtask 1: 0 / 15
• Subtask 2: 0 / 35
• Subtask 3: 0 / 60