Submission #768794

#	Time	Username	Problem	Language	Result	Execution time	Memory
768794		1075508020060209tc	Janjetina (COCI21_janjetina)	C++14	50 / 110	96 ms	15876 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];
}
int ans;
vector<pair<int,int>>ee[200005];
int dph[200005];
void dfs(int nw,int pa,int mxv){
    if(pa&&mxv-dph[nw]>=K){
        ans++;
    }
    for(int i=0;i<ee[nw].size();i++){
        int v=ee[nw][i].first;
        if(v==pa){continue;}
        int w=ee[nw][i].second;
        dph[v]=dph[nw]+1;
        dfs(v,nw,max(mxv,w) );
    }
}
void solve(){
ans=0;
for(int i=1;i<=n;i++){
    dph[i]=0;
    dfs(i,0,0);
}
cout<<ans<<endl;
exit(0);
}

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;
    int a=e[i].second.first;int b=e[i].second.second;int c=e[i].first;
    ee[a].push_back({b,c});
    ee[b].push_back({a,c});
}

if(n<=1000){
    solve();
}

sort(e+1,e+n-1+1);
for(int i=1;i<=n;i++){
    uf[i]=i;
    usz[i]=1;
}
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+=max(0ll,min((W-K)-j+1ll,usz[b]));
    }
    mrg(a,b);
  //  cout<<W<<" "<<ans<<endl;
}
cout<<ans*2<<endl;

}

Compilation message (stderr)

Main.cpp: In function 'void dfs(long long int, long long int, long long int)':
Main.cpp:27:18: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   27 |     for(int i=0;i<ee[nw].size();i++){
      |                 ~^~~~~~~~~~~~~~

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