제출 #648262

#제출 시각아이디문제언어결과실행 시간메모리
648262smirichto경주 (Race) (IOI11_race)C++17
0 / 100
3 ms4948 KiB
/* STAY ORGANIZED CHANGE YOUR APPROACH */ #include<bits/stdc++.h> using namespace std; typedef long long ll ; typedef long double ld ; #define FAST ios::sync_with_stdio(0), cin.tie(0),cout.tie(0) #define pb push_back #define pi pair<ll,ll> #define pll pair<ll,ll> #define yes cout<<"Yes"<<endl; #define no cout<<"No"<<endl; #define flag cout<<"hi"<<endl; #define fr(i,a,b) for(ll i = a;i < (ll)b;i++) #define rfr(i,a,b) for(ll i = a;i > (ll)b;i--) #define F first #define S second #define all(x) (x).begin(), (x).end() #define alll(x) ((x).begin()+1), (x).end() #define MOD mod #define endl '\n' const ll mod = 1e9+7 ; //void io(){ios::sync_with_stdio(false) ;cin.tie(NULL) ;freopen("grader.in.4","r",stdin) ;freopen("grader.out.4","w",stdout) ; //} void dbg(vector<ll> tab){for(auto it : tab) cout<<it<<" ";cout<<endl;} void dbgg(pi p){cout<<p.F<<" "<<p.S<<endl;} void dbgpi(vector<pi> tab){for(auto it : tab) dbgg(it) ;} template<class T> bool ckmax(T& a, const T& b){return a < b ? a = b, 1 : 0;} template<class T> bool ckmin(T& a, const T& b){return a > b ? a = b, 1 : 0;} template<class T> void add(T& a, const T& b){a = a + b ; if(a>mod) a-= mod ;} void nop(){cout<<-1<<endl;return;} const ll inf = 1e9 +1; const ll N = 2e5+5 , MAXN = 1e5+5 , NAX = 1001 ; ll n , k ; vector<pi> v[N] ; ll len[N] , sz[N] , vis[N] ; void get_sz(ll node , ll oj) { sz[node] = 1 ; for(auto [it,i] : v[node]){ if(it==oj || vis[it]) continue ; get_sz(it,node) ; sz[node] += sz[it] ; } } ll get_centro(ll node , ll oj , ll m) { for(auto [it,i] : v[node]){ if(!vis[it] && it!=oj && sz[it]>m/2) return get_centro(it,node,m) ; } return node ; } map<ll,ll> mp , exist ; ll ans = 1e9 ; void get_cnt(ll node , ll oj , ll ok , ll curr_len, ll d = 1) { // cout<<node<<" "<<curr_len<<endl; if(ok){ if(k-curr_len>=0 && exist[k-curr_len]){ // cout<<node<<" "<<d<<" "<<k-curr_len<<endl; ckmin(ans, d+mp[k-curr_len]) ; } } else{ if(exist[curr_len]) ckmin(mp[curr_len] , d) ; else{ mp[curr_len] = d; exist[curr_len] = 1 ; } } for(auto [it,i] : v[node]){ if(vis[it] || it==oj) continue ; get_cnt(it,node,ok,curr_len+len[i],d+1) ; } } void build(ll node = 0) { get_sz(node , node) ; ll centroid = get_centro(node , node , sz[node]) ; mp.clear() ; exist.clear() ; // cout<<centroid<<endl; vis[centroid] = 1 ; for(auto [it,i] : v[centroid]){ get_cnt(it,node,1 , len[i]) ; get_cnt(it,node,0 , len[i]) ; } for(auto [it,i] : v[centroid]){ if(!vis[it]) build(it) ; } } int best_path(int nn, int kk, int edges[][2], int weights[]) { n = nn ; k = kk ; for(int i = 1 ; i<n ; i++){ int x = edges[i][0] , y = edges[i][1] ; v[x].pb({x,i}) ; v[y].pb({y,i}) ; len[i] = weights[i] ; } build() ; return ans >=1e9 ? -1:ans ; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...