Submission #226503

#	Time	Username	Problem	Language	Result	Execution time	Memory
226503		mohamedsobhi777	경주 (Race) (IOI11_race)	C++14	100 / 100	2357 ms	129404 KiB

race

#include "race.h"
#include<bits/stdc++.h>

using namespace std ; 
const int NN = 1e6 + 7 ; 

long long n , k ; 
long long ans = 10000000000000 ; 
vector<pair<long long , long long > > adj[NN] ; 
long long hei[NN] , ldr[NN] , sz[NN]; 
long long fr[NN] , ls[NN] , ver[NN]; 
map<long long , map<long long , long long >  > anss ; 
int t = 1; 

int dfz(int x , int p , long long h, int l = 1 ){
    ver[t] = x ; 
    fr[x] = t++ ; 
    int ret = 1; 
    hei[x] = h ; 
    ldr[x] = l ; 
    for(auto u : adj[x]){
        if(u.first==p)continue ; 
        ret+=dfz(u .first, x , h + u.second , l+1 ) ; 
    }
    ls[x] = t++ ; 
    return sz[x] = ret ; 
}

int dfs(int x , int p , bool keep){
    int big = 0 ; 
    for(auto u : adj[x]){
        if(u.first==p)continue ;
        if(sz[u.first] > sz[big]){
            big = u.first ; 
        }
    }
    for(auto u : adj[x]){
        if(u.first ==p || u.first ==big)continue ;     
        dfs(u.first, x , 0) ; 
    }
    if(big){
        dfs(big , x , 1 ) ; 
    }
    for(auto u : adj[x]){
        if(u.first==p || u.first == big)continue ;
        vector<int> v ;
        for(int j = fr[u.first] ; j < ls[u.first] ;j ++ ){
            if( ver[j] ){
                long long he = hei[ver[j]] ; 
                long long dl = ldr[ver[j]] ; 
                long long drem = k - (hei[ver[j]] - hei[x] ) ;
                v.push_back(j) ; 
                if( drem <=0)continue ; 
                for(auto u : anss[ hei[x] + drem ]){
                    if(u.second){
                        ans = min(ans , u.first - ldr[x] + dl - ldr[x]) ; 
                    }
                }
            }
        }
        for(auto e : v){
            anss[hei[ver[e]]][ ldr[ver[e]] ]++ ; 
        }
    }    
    anss[hei[x]][ldr[x]]++;         
    for(auto u: anss[hei[x] + k] ){
        if(u.second){
            ans = min(ans , u.first - ldr[x] ) ; 
        }
    }
    if(!keep){
        for(int i = fr[x] ; i < ls[x] ; i++){
            anss[hei[ver[i]]][ldr[ver[i]]] -- ; 
        }
    }
}

int best_path(int N, int K, int H[][2], int L[])
{
    n = N ;
    k = K ;
    bool zez = 0 ; 
    for(int i = 0 ;i < n-1 ;i++){
        adj[H[i][0]+1].push_back({H[i][1]+1 , L[i]}) ; 
        adj[H[i][1]+1].push_back({H[i][0]+1, L[i]}) ; 
        zez|=!L[i] ; 
    }
    dfz(1 , 1 , 0) ; 
    dfs(1 , 1 , 0) ; 
    if(ans==10000000000000) ans = -1 ; 
    if(!k&&zez)ans = 1 ; 
    return ans ; 
}

Compilation message (stderr)

race.cpp: In function 'int dfs(int, int, bool)':
race.cpp:49:27: warning: unused variable 'he' [-Wunused-variable]
                 long long he = hei[ver[j]] ; 
                           ^~
race.cpp:76:1: warning: no return statement in function returning non-void [-Wreturn-type]
 }
 ^

• Subtask 1: 9 / 9
• Subtask 2: 12 / 12
• Subtask 3: 22 / 22
• Subtask 4: 57 / 57