Submission #495723

#	Time	Username	Problem	Language	Result	Execution time	Memory
495723		Pietra	Race (IOI11_race)	C++14	Compilation error	0 ms	0 KiB

race

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

Compilation message (stderr)

/usr/bin/ld: /tmp/ccnPU9sV.o: in function `main':
race.cpp:(.text.startup+0x0): multiple definition of `main'; /tmp/cctU9hzU.o:grader.cpp:(.text.startup+0x0): first defined here
/usr/bin/ld: /tmp/cctU9hzU.o: in function `main':
grader.cpp:(.text.startup+0x28): undefined reference to `best_path(int, int, int (*) [2], int*)'
collect2: error: ld returned 1 exit status