Submission #1095209

#	Time	Username	Problem	Language	Result	Execution time	Memory
1095209		0pt1mus23	Janjetina (COCI21_janjetina)	C++14	110 / 110	379 ms	20096 KiB

Main

#include <bits/stdc++.h>
using namespace std;

#define int long long
#define endl '\n'
#define ins insert
#define pb push_back
#define putr(x) cout<<x<<endl;return;
#define all(x) x.begin(),x.end()
#define _ << " " <<  
const int   mod = 1e9+7 ,
            sze= 1e5 +23 ,
            inf = INT_MAX ,
            L = 31 ;

int arr[sze];
int ans=0;
int T[sze +23];
int k;
vector<pair<int,int>> graph[sze];

void upd(int node,int x){
    for(++node;node<=sze;node += (node & -node)){
        T[node]+=x;
    }
}
int qry(int node){
    int sum=0;
    for(++node;node>0;node -= (node & -node)){
        sum+=T[node];
    }
    return sum;
}


int cmp(pair<int,int >x, pair<int,int> y){
    if(x.second != y.second){
        return x.second < y.second;
    }
    return x.first < y.first;
}
vector<pair<int,int>> event;
int depth[sze];
int sub[sze];
int sil[sze];
int curr=0;
void dfs1(int node,int par){
    curr++;
    sub[node]=1;
    for(auto [v,w]:graph[node]){
        if(v!=par && !sil[v]){
            depth[v]=depth[node]+1;
            dfs1(v,node);
            sub[node]+=sub[v];
        }
    }
}
int dfs2(int node,int par){
    for(auto [v,w]:graph[node]){
        if(v!=par && !sil[v]){
            if(sub[v]*2>curr){
                return dfs2(v,node);
            }
        }
    }
    return node;
}
void dfs3(int node,int par,int mx){
    event.pb({node,mx});
    for(auto [v,w]:graph[node]){
        if(v!=par && !sil[v]){
            dfs3(v,node,max(mx,w));
        }
    }
}

void decomp(int node){
    curr=0;
    depth[node]=0;
    dfs1(node,-1);
    int centroid = dfs2(node,-1);
    
    curr=0;
    depth[centroid]=0;
    dfs1(centroid,-1);
    dfs3(centroid,-1,0);

    sort(all(event),cmp);
    for(auto [v,w]:event){
        ans+=qry(w - depth[v] - k);
        upd(depth[v],1);
    }
    for(auto [v,w]:event){
        upd(depth[v],-1);
    }
    event.clear();
    for(auto [v,w]:graph[centroid]){
        if(!sil[v]){
            dfs3(v,centroid,w);
            sort(all(event),cmp);
            for(auto ev:event){
                ans-=qry(ev.second - depth[ev.first] -k);
                upd(depth[ev.first],1);
            }
            for(auto ev:event){
                upd(depth[ev.first],-1);
            }
            event.clear();
        }
    }
    sil[centroid]=1;
    for(auto [v,w]:graph[centroid]){
        if(!sil[v]){
            decomp(v);
        }
    }
}

void opt1z(){
    int n;
    cin>>n>>k;
    for(int i=1;i<n;i++){
        int u,v,w;
        cin>>u>>v>>w;
        graph[u].pb({v,w});
        graph[v].pb({u,w});
    }
    decomp(1);
    cout<<ans*2LL<<endl;
}

signed main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
 
    int tt = 1;
    // cin>>tt;
    while(tt--){
        opt1z();
    }
 
    return 0;
}

Compilation message (stderr)

Main.cpp: In function 'void dfs1(long long int, long long int)':
Main.cpp:50:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   50 |     for(auto [v,w]:graph[node]){
      |              ^
Main.cpp: In function 'long long int dfs2(long long int, long long int)':
Main.cpp:59:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   59 |     for(auto [v,w]:graph[node]){
      |              ^
Main.cpp: In function 'void dfs3(long long int, long long int, long long int)':
Main.cpp:70:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   70 |     for(auto [v,w]:graph[node]){
      |              ^
Main.cpp: In function 'void decomp(long long int)':
Main.cpp:89:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   89 |     for(auto [v,w]:event){
      |              ^
Main.cpp:93:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   93 |     for(auto [v,w]:event){
      |              ^
Main.cpp:97:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   97 |     for(auto [v,w]:graph[centroid]){
      |              ^
Main.cpp:112:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  112 |     for(auto [v,w]:graph[centroid]){
      |              ^

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