Submission #242773

#TimeUsernameProblemLanguageResultExecution timeMemory
242773michaoRace (IOI11_race)C++14
21 / 100
3074 ms12024 KiB
#include <bits/stdc++.h> #define ll long long int #define mp make_pair #define pb push_back #define ld long double #define pii pair<int,int> #define sz(x) (int)x.size() #define piii pair<pii,pii> #define precise cout<<fixed<<setprecision(10) #define st first #define nd second #define ins insert #define vi vector<int> #define BOOST ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0) using namespace std; const int MAX=2e5+5; const int inf=1e9+9; vector<pii>P[MAX]; int gle[MAX]; int dist[MAX]; int ans=inf; void brut(int u,int fa,int k) { if (fa==-1)gle[u]=0,dist[u]=0; if (dist[u]==k)ans=min(ans,gle[u]); for (auto it:P[u]) { if (it.st!=fa) { gle[it.st]=gle[u]+1; dist[it.st]=dist[u]+it.nd; brut(it.st,u,k); } } } void func(int n,int k) { for (int i=1;i<=n;i++)brut(i,-1,k); } int best_path(int n,int k,int h[][2],int l[]) { for (int i=0;i<n-1;i++) P[h[i][0]].pb(mp(h[i][1],l[i])),P[h[i][1]].pb(mp(h[i][0],l[i])); func(n,k); if (ans==inf)ans=-1; return 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...