제출 #749145

#제출 시각아이디문제언어결과실행 시간메모리
749145anaduguleanu경주 (Race) (IOI11_race)C++14
0 / 100
7 ms9996 KiB
#include <iostream> #include <vector> #include <map> #define NMAX 200000 #define INF 1000000000000000000 using namespace std; ///ifstream cin ("c.in"); ///ofstream cout ("c.out"); vector <pair <int, int>> graph[NMAX + 10]; map <long long, long long> mp; int ok, mark[NMAX + 10], sz[NMAX + 10]; long long k, ans = INF; int solve(int node, int parent, long long depth, long long cost) { if (cost > k) return 0; if (ok == 1) { if (mp[cost] == 0) mp[cost] = depth; else mp[cost] = min(mp[cost], depth); } else { if (mp[k - cost] != 0) ans = min(ans, depth + mp[k - cost] - 2); } for (auto it: graph[node]) if (it.first != parent && mark[it.first] == 0) solve(it.first, node, depth + 1, cost + it.second); } int findCentroid(int node, int s, int parent) { for (auto it: graph[node]) if (it.first != parent && mark[it.first] == 0 && sz[it.first] * 2 > s) return findCentroid(it.first, s, node); return node; } int dfs(int node, int parent) { sz[node] = 1; for (auto it: graph[node]) if (it.first != parent && mark[it.first] == 0) sz[node] = sz[node] + dfs(it.first, node); return sz[node]; } void centroid(int node) { int aux = dfs(node, -1), cent = findCentroid(node, aux, -1); mp.clear(); mp[0] = 1; mark[cent] = 1; for (auto it: graph[cent]) if (mark[it.first] == 0) { ok = 0; solve(it.first, -1, 2, it.second); ok = 1; solve(it.first, -1, 2, it.second); } for (auto it: graph[cent]) if (mark[it.first] == 0) centroid(it.first); } int best_path(int N, int K, int H[][2],int L[]) { k = K; for (int i = 0; i < N - 1; i++) { graph[H[i][0] + 1].push_back({H[i][1] + 1, L[i]}); graph[H[i][1] + 1].push_back({H[i][0] + 1, L[i]}); } centroid(1); if (ans == INF) return -1; else return ans; }

컴파일 시 표준 에러 (stderr) 메시지

race.cpp: In function 'int solve(int, int, long long int, long long int)':
race.cpp:32:1: warning: control reaches end of non-void function [-Wreturn-type]
   32 | }
      | ^
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...