Submission #172412

#	Time	Username	Problem	Language	Result	Execution time	Memory
172412		lobo_prix	Race (IOI11_race)	C++17	Compilation error	0 ms	0 KiB

race

    #include <bits/stdc++.h>
    #include "race.h"
     
    using namespace std;using f64 = double;using i64=long long;using u64=unsigned long long;
    template<typename T> using Arr=vector<T>;
    #define hfor(v, s, e) for(int v=(s);(s)<=v&&v<(e);++v)//half-opened range
    #define hfori(v, s, e) for(int v=(e)-1;(s)<=v&&v<(e);--v)//inversion
    #define hforo(v, s, e) int v=(s);for(;(s)<=v&&v<(e);++v)//out declaration
    #define hforoi(v, s, e) int v=(e)-1; for(;(s)<=v&&v<(e);--v)
    #define cfor(v, s, e) hfor(v,(s),(e)+1)//closed range
    #define cfori(v, s, e) hfori(v,(s),(e)+1)
    #define cforo(v, s, e) hforo(v,(s),(e)+1)
    #define cforoi(v, s, e) hforoi(v,(s),(e)+1)
    #define rep(v,x) hfor(v,0,(x))
    #define repi(v,x) hfori(v,0,(x))
    #define repo(v,x) hforo(v,0,(x))
    #define all(x) (x).begin(),(x).end()
    #define sz(x) ((int)(x).size())
    #define pushb push_back
    #define pushf push_front
    #define popb pop_back
    #define popf pop_front
    #define empl emplace
    #define emplb emplace_back
    #define emplf emplace_front
    #define fi first
    #define se second
    #define cxp constexpr
    #define PQ std::priority_queue
     
    #ifndef DEBUG
    	#pragma GCC optimize ("Ofast")
    	auto __PRE_RUN__=(ios::sync_with_stdio(0), cin.tie(0), cout.tie(0),(cout<<fixed<<setprecision(11)), 0);
    #endif
     
    template<typename T> cxp T inf() { return numeric_limits<T>::max() / 2; }
    auto mapf(auto a, auto f){for(auto& x:a)x=f(x); return a;}
    int rd(int lb, int ub){static mt19937 rng(time(0)^i64(new int)); return uniform_int_distribution<int>(lb, ub-1)(rng);}
    int rd(int ub=inf<int>()){return rd(0,ub);}
    const f64 pi=acosl(-1);
    #define endl '\n'//not interactive?
    #define int i64//MLE?
    using pint = pair<int,int>;
    using tint = tuple<int,int,int>;
     
    const int N=200000;
    int n,k;
    Arr<pint> t[N];
    int s[N];
    bool d[N];
     
    int ct(int v, int sz_tot){
    	int mx=-1;
    	for(auto i:t[v]){
    		if(d[i.fi])
    			continue;
    		if(mx<0 or s[mx]<s[i.fi])
    			mx=i.fi;
    	}
    	if(mx<0 or s[mx]*2<=sz_tot)
    		return v;
    	d[v]=true;
    	int ret=ct(mx, sz_tot);
    	d[v]=false;
    	return ret;
    }
     
    int recalc(int v){
    	s[v]=1;
    	d[v]=true;
    	for(auto i:t[v])
    		if(!d[i.fi])
    			s[v]+=recalc(i.fi);
    	d[v]=false;
    	return s[v];
    }
     
    void get_paths(int v, int dist, int cnt, multiset<pint>& z){
    	z.insert({dist,cnt});
    	d[v]=true;
    	for(auto i:t[v])
    		if(!d[i.fi])
    			get_paths(i.fi, dist+i.se, cnt+1, z);
    	d[v]=false;
    }
     
    int f(int v){
    	v=ct(v, s[v]);
    	int ret=inf<int>();
     
    	multiset<pint> z;
    	for(auto i:t[v]){
    		multiset<pint> y;
    		if(!d[i.fi])
    			get_paths(i.fi, i.se, 1, y);
     
    		for(auto j:y){
    			auto it = z.lower_bound({k-j.fi,0});
    			if(it!=z.end() and it->fi==k-j.fi)
    				ret=min(ret, j.se+it->se);
    		}
    		z.insert(all(y));
    	}
     
    	recalc(v);
    	d[v]=true;
    	for(auto i:t[v])
    		if(!d[i.fi])
    			ret=min(ret, f(i.fi));
    	d[v]=false;
    	return ret;
    }
	int best_path(int N, int K, int H[][2], int L[]) {
      rep(i,n-1){
        t[h[i][0]].pushb({h[i][1],l[i]});
        t[h[i][1]].pushb({h[i][0],l[i]});
      }
      recalc(0);
      return f(0);
    }

Compilation message (stderr)

race.cpp: In function 'i64 best_path(i64, i64, i64 (*)[2], i64*)':
race.cpp:115:11: error: 'h' was not declared in this scope
         t[h[i][0]].pushb({h[i][1],l[i]});
           ^
race.cpp:115:35: error: 'l' was not declared in this scope
         t[h[i][0]].pushb({h[i][1],l[i]});
                                   ^