oj.uz

Submission #768786

# Submission time Handle Problem Language Result Execution time Memory
768786 2023-06-28T15:33:02 Z 1075508020060209tc Janjetina (COCI21_janjetina) C++14
0 / 110
 1 ms 212 KB 
#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.0

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

Subtask #2
0 / 35.0

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

Subtask #3
0 / 60.0

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