제출 #666912

#제출 시각아이디문제언어결과실행 시간메모리
666912Bogdan1110경주 (Race) (IOI11_race)C++14
9 / 100
99 ms54044 KiB
#include <bits/stdc++.h> #include "race.h" #define FAST {ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);} #define FILES {freopen("input.txt", "r", stdin);freopen("output.txt", "w", stdout);} #define ll long long #define ull unsigned long long #define pqueue priority_queue #define pb push_back #define fi first #define se second #define ld long double #define pii pair<int,int> #define pll pair<long long,long long> #define all(a) (a).begin(), (a).end() #define mp make_pair using namespace std; #include <ext/pb_ds/assoc_container.hpp> #include <ext/pb_ds/tree_policy.hpp> using namespace __gnu_pbds; #define ordered_set tree<pll, null_type,less<pll>, rb_tree_tag,tree_order_statistics_node_update> // order_of_key -> # less than k // find_by_order -> k-th element // pq max element const double eps = 0.00000001; const int NMAX = 2000010; const ll inf = LLONG_MAX/3; const ll modi = 998244353; int K; int visited[NMAX]; vector<pii>al[NMAX]; int res = INT_MAX; map<int,int> dfs(int node, int dep, int kol) { map<int,int>r; r[kol] = dep; if ( visited[node] ) { return r; } visited[node] = 1; for (auto u : al[node]) { if ( visited[u.fi] ) continue; map<int,int>t = dfs(u.fi, dep+1, kol + u.se); if ( t.size() > r.size() ) swap(t,r); for (auto k:t) { if ( r.find(k.fi) != r.end() ) { r[k.fi] = min(r[k.fi], k.se); } else { r[k.fi] = k.se; } } } if ( r.find(kol+K) != r.end() ) res = min(res, r[kol+K] - dep); //cout << node << ' ' << dep << ' '<< kol << endl; return r; } int best_path(int n, int k, int h[][2], int l[]) { K = k; for (int i = 0 ; i < n-1 ; i++ ) { al[h[i][0]].pb({h[i][1],l[i]}); al[h[i][1]].pb({h[i][0],l[i]}); } for (int i = 0; i < n ; i++ ) { if ( al[i].size() == 1 ) { dfs(i,0,0); break; } } if ( res == INT_MAX) return -1; return res; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...