제출 #1000788

#제출 시각아이디문제언어결과실행 시간메모리
1000788uranhishig경주 (Race) (IOI11_race)C++14
21 / 100
3036 ms29520 KiB
#include <bits/stdc++.h> using namespace std; typedef long long ll; typedef vector<int> vi; typedef vector<ll> vl; typedef vector<vi> vvi; typedef vector<vl> vvl; typedef pair<int,int> pii; typedef pair<double, double> pdd; typedef pair<ll, ll> pll; typedef vector<pii> vii; typedef vector<pll> vll; typedef double dl; #define f first #define s second #define mp make_pair #define pb push_back #define all(a) (a).begin(),(a).end() #define sz(x) (int)x.size() #define mid(l,r) ((r+l)/2) #define left(node) (node*2) #define right(node) (node*2+1) #define mx_int_prime 999999937 #define mod 1000000007 #define mem(a,b) memset(a, b, sizeof(a) ) #define gcd(a,b) __gcd(a,b) #define lcm(a, b) (a * b) / gcd(a, b) #define sqr(a) ((a) * (a)) #define faster ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0); #define fastio cin.tie(0)->sync_with_stdio(0) #define print(x) cout << x << "\n" #define rep(i, n) for(int i = 0; i < (n); i++) #define rep1(i, n) for(int i = 1; i <= (n); i++) #define yes cout << "YES" << endl; #define no cout << "NO" << endl; const int MAXN = 1e6; vector<pair<int, int>> adj[MAXN]; bool visited[MAXN]; int mi = INT_MAX; void dfs(int node, int x, int y, int z) { visited[node] = true; if (x == y) { mi = min(mi, z); } else { for (auto neighbor : adj[node]) { int nextCity = neighbor.f; int length = neighbor.s; if (!visited[nextCity] && x + length <= y) { dfs(nextCity, x + length, y, z + 1); } } } visited[node] = false; } int best_path(int N, int K, int H[][2], int L[]) { rep(i, N-1) { int city1 = H[i][0], city2 = H[i][1], length = L[i]; adj[city1].emplace_back(city2, length); adj[city2].emplace_back(city1, length); } mi = INT_MAX; for (int st = 0; st < N; st++) { memset(visited, false, sizeof(visited)); dfs(st, 0, K, 0); } if (mi == INT_MAX) { return -1; } else { return mi; } }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...