Submission #495726

#	Time	Username	Problem	Language	Result	Execution time	Memory
495726		Pietra	Race (IOI11_race)	C++14	100 / 100	597 ms	34016 KiB

race

    #include<bits/stdc++.h>
    using namespace std ; 
    #include "race.h"
     
    const int inf = 1e9 + 5 ; 
    const int maxn = 2e5 + 5 ; 
    const int MAXN = 1e6 + 5 ; 
     
    int sz[maxn], mark[maxn], ans, n, k, f[MAXN] ;
    vector<pair<int,int>> grafo[maxn] ; 
     
    void dfs(int v, int p){
     
    	sz[v] = 1 ; 
     
    	for(auto a : grafo[v]){
    		if(a.first == p || mark[a.first]) continue ; 
    		dfs(a.first, v) ; 
    		sz[v] += sz[a.first] ; 
    	}
     
    }
     
    int find_cent(int v, int p, int szz){
     
    	for(auto a : grafo[v]){
    		if(a.first == p || mark[a.first] || 2*sz[a.first] <= szz) continue ;
    		return find_cent(a.first, v, szz) ;  
    	}
     
    	return v ; 
     
    }
     
    void make_count(int type, int v, int p, int dist, int lvl){
     
    	if(dist > k) return ; 
     
    	if(type == -1) f[dist] = inf ; 
     
    	else f[dist] = min(f[dist], lvl) ; 
     
    	for(auto a : grafo[v]){
    		if(a.first == p || mark[a.first]) continue ; 
    		make_count(type, a.first, v, dist + a.second, lvl + 1) ; 
    	}
     
    }
     
    void add(int v, int p, int dist, int lvl){
     
    	if(dist > k) return ; 
     
    	ans = min(ans, f[k-dist] + lvl) ; 
     
    	for(auto a : grafo[v]){
    		if(a.first == p || mark[a.first]) continue ; 
    		add(a.first, v, dist + a.second, lvl+1) ; 
    	}
     
    }
     
    void make_graph(int v, int p){
     
    	dfs(v, p) ; 
     
    	int c = find_cent(v, p, sz[v]) ; 
     
    	mark[c] = 1 ; 
    	f[0] = 0 ; 
     
    	for(auto a : grafo[c]){
    		if(a.first == p || mark[a.first]) continue ; 
    		add(a.first, c, a.second, 1) ; 
    		make_count(0, a.first, c, a.second, 1) ; 
    	}
     
    	for(auto a : grafo[c]){
    		if(a.first == p || mark[a.first]) continue ; 
    		make_count(-1, a.first, c, a.second, 1) ; 
    	}
     
    	for(auto a : grafo[c]){
    		if(a.first == p || mark[a.first]) continue ; 
    		make_graph(a.first, c) ; 
    	}
     
    }
     
    int best_path(int N, int K, int H[maxn][2], int L[maxn]) {
      
      for(int i = 0 ; i < N - 1 ; i++){
      	grafo[H[i][0]].push_back({H[i][1], L[i]}) ; grafo[H[i][1]].push_back({H[i][0], L[i]}) ; 
      }
     
      k = K ; 
     
      for(int i = 1 ; i <= K ; i++) f[i] = inf ; 
      ans = inf ; 
      make_graph(0, -1) ; 
      
      return (ans == inf ? -1 : ans) ; 
     
    }
     
    // int32_t main(){
     
    // 	ans = inf ; 
     
    // 	cin >> n >> k ; 
     
    // 	for(int i = 0 ; i < n-1 ; i++){
    // 		int a, b, c ; 
    // 		cin >> a >> b >> c ; 
    // 		grafo[a].push_back({b, c}), grafo[b].push_back({a, c}) ; 
    // 	}
     
    // 	for(int i = 1 ; i <= k ; i++) f[i] = inf ; 
     
    //     make_graph(0, -1) ; 
      
    //     cout << ans << "\n" ; 
     
    // }

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