Submission #788019

#	Time	Username	Problem	Language	Result	Execution time	Memory
788019		manizare	Janjetina (COCI21_janjetina)	C++14	110 / 110	277 ms	52608 KiB

Main

#include <bits/stdc++.h>  
 
#define pii pair <int,int>  
#define F first  
#define S second  
#define all(a) a.begin(),a.end()  
#define pb push_back 
#define ll long long  
using namespace std ;  
const int maxn = 5e5  +10  , inf  = 1e9 ;  
int mark[maxn] , t[maxn] , c[maxn]  , s =0 , n , k ; 
vector <int> to[maxn] ;vector <pii> G[maxn] ;    
vector <int> fen[maxn] ;  
vector <pair <pii  , int> > vec;  
int maxh = 0 , cnt = 1 , sz ;  
 
void find(int v , int p){ 
    t[v] = 1;  
    bool ok = 0 ; 
    for(int i = 0 ; i < G[v].size() ; i++){ 
        int u = G[v][i].S , w = G[v][i].F ;  
        if(u == p || mark[u] == 1)continue ; 
        find(u , v) ; 
        t[v] += t[u] ; 
        if(t[u] > sz/2){ 
            ok = 1 ; 
        }   
    } 
    if((sz-t[v]) > sz/2)ok = 1;  
    if(ok == 0)s = v ;  
} 
void bui(int v , int p , int dis , int mx , int jd){ 
    vec.pb({{mx , dis} , v}); 
    c[v] = jd ;  
    while(to[jd].size() <= (dis+1))to[jd].pb(0) ,fen[jd].pb(0) ; 
    to[jd][dis]++; 
    maxh  = max(maxh , dis) ;  
    for(int i =0 ; i < G[v].size(); i++){ 
        int w = G[v][i].F , u = G[v][i].S ; 
        if(u == p || mark[u] == 1)continue ; 
        bui(u , v , dis+1 ,  max(mx , w) , jd) ; 
    } 
} 
 
void upd(int x , int y , int val){ 
    y++; 
    while(y < ((int)fen[x].size())){ 
        fen[x][y] += val ; 
        y += (y&-y) ; 
    } 
}  
int que(int x, int y){ 
    y++; 
    int ans =0 ;  
    y = min(y , (int)fen[x].size() - 1)  ;
    while(y>0){ 
        ans += fen[x][y] ;  
        y -= (y&-y) ; 
    } 
    return ans ; 
} 
int yep(int x , int p){ 
    int t =1 ; 
    for(int i = 0 ; i <G[x].size() ; i++){ 
        int u = G[x][i].S ; 
        if(p == u || mark[u] == 1)continue ;  
        t += yep(u , x) ; 
    } 
    return t ; 
} 
ll ans =0 ; 
void sen(int v){ 
    maxh = 0 ;s = -1 ;  
    find(v , 0) ;maxh++; 
    mark[s] = 1;  
    c[s] = -1 ;  
    vec.clear(); 
    for(int i = 0 ; i < G[s].size() ; i++){ 
        int u = G[s][i].S ;  
        to[i].clear() ; 
        fen[i].clear(); 
        if(mark[u] == 1)continue ;
        bui(u , s , 1 , G[s][i].F , i); 
        fen[i].pb(0);
        for(int j = 0 ; j < to[i].size() ; j++){ 
            upd(i , j , to[i][j]) ; 

        } 
    } 
    fen[(int)G[s].size()].clear();  
    fen[(int)G[s].size()].pb(0) ;  
    for(int i =0 ; i <= vec.size() ; i++){ 
        fen[(int)G[s].size()].pb(0) ;  
    } 
    for(int i =0  ;i < vec.size() ; i++){ 
        upd((int)G[s].size() , vec[i].F.S , 1 ); 

    } 
    upd((int)G[s].size() , 0 , 1) ; 
    sort(all(vec));reverse(all(vec)) ; 
    for(int i = 0 ; i < vec.size() ; i++){ 
        ans = (ans + que((int)G[s].size() , vec[i].F.F - vec[i].F.S - k) - que(c[vec[i].S] , vec[i].F.F - vec[i].F.S - k)); 
        upd((int)G[s].size() , vec[i].F.S , -1);
        upd(c[vec[i].S] , vec[i].F.S , -1) ;
    }  
    int ls = s;  
    for(int i =0 ; i < G[ls].size() ; i++){ 
        int u = G[ls][i].S ; 
        if(mark[u] == 1)continue ; 
        sz = yep(u ,ls) ;  
        sen(u ) ; 
    } 
} 
 
signed main(){ 
    ios::sync_with_stdio(0);cin.tie(0) ;  
    cin >> n >> k ; 
    for(int i = 1 ; i < n;  i++){ 
        int v, u  , w ; 
        cin >> v >> u>> w ;  
        G[v].pb({w , u}) ; 
        G[u].pb({w , v}) ; 
    } 
    sz = n ; 
    sen(1) ;  
    cout << ans * 2 << "\n" ; 
} 
/* 
 
3 1  
1 2 3  
1 3 2 
 
 
 
4 1  
1 2 1  
2 3 2  
3 4 3 
 
*/

Compilation message (stderr)

Main.cpp: In function 'void find(int, int)':
Main.cpp:20:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   20 |     for(int i = 0 ; i < G[v].size() ; i++){
      |                     ~~^~~~~~~~~~~~~
Main.cpp:21:29: warning: unused variable 'w' [-Wunused-variable]
   21 |         int u = G[v][i].S , w = G[v][i].F ;
      |                             ^
Main.cpp: In function 'void bui(int, int, int, int, int)':
Main.cpp:35:25: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   35 |     while(to[jd].size() <= (dis+1))to[jd].pb(0) ,fen[jd].pb(0) ;
      |           ~~~~~~~~~~~~~~^~~~~~~~~~
Main.cpp:38:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   38 |     for(int i =0 ; i < G[v].size(); i++){
      |                    ~~^~~~~~~~~~~~~
Main.cpp: In function 'int yep(int, int)':
Main.cpp:64:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   64 |     for(int i = 0 ; i <G[x].size() ; i++){
      |                     ~~^~~~~~~~~~~~
Main.cpp: In function 'void sen(int)':
Main.cpp:78:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   78 |     for(int i = 0 ; i < G[s].size() ; i++){
      |                     ~~^~~~~~~~~~~~~
Main.cpp:85:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   85 |         for(int j = 0 ; j < to[i].size() ; j++){
      |                         ~~^~~~~~~~~~~~~~
Main.cpp:92:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<std::pair<int, int>, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   92 |     for(int i =0 ; i <= vec.size() ; i++){
      |                    ~~^~~~~~~~~~~~~
Main.cpp:95:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<std::pair<int, int>, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   95 |     for(int i =0  ;i < vec.size() ; i++){
      |                    ~~^~~~~~~~~~~~
Main.cpp:101:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<std::pair<int, int>, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  101 |     for(int i = 0 ; i < vec.size() ; i++){
      |                     ~~^~~~~~~~~~~~
Main.cpp:107:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  107 |     for(int i =0 ; i < G[ls].size() ; i++){
      |                    ~~^~~~~~~~~~~~~~

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