제출 #480072

#제출 시각아이디문제언어결과실행 시간메모리
480072LeMur경주 (Race) (IOI11_race)C++17
0 / 100
5 ms4940 KiB
/////////////////////////////// _LeMur_ #define _CRT_SECURE_NO_WARNINGS #include "race.h" #include <unordered_map> #include <unordered_set> #include <algorithm> #include <iostream> #include <cstring> #include <cassert> #include <chrono> #include <random> #include <bitset> #include <cstdio> #include <vector> #include <string> #include <stack> #include <queue> #include <ctime> #include <cmath> #include <list> #include <map> #include <set> using namespace std; const int N = 200005; const int inf = 1000 * 1000 * 1000; const int mod = 1000 * 1000 * 1000 + 7; mt19937 myrand(chrono::steady_clock::now().time_since_epoch().count()); vector < pair<int, int> > g[N]; int answ = -1; bool used[N]; int sz[N]; int nn = 0; int k; void dfs_sz(int v, int p) { nn++; sz[v] = 1; for (int i = 0; i < (int)g[v].size(); i++) { int to = g[v][i].first; if (to == p) continue; if (used[to]) continue; dfs_sz(to, v); sz[v] += sz[to]; } } int find_center(int v, int p) { int mx_sz = -1, gag; for (int i = 0; i < (int)g[v].size(); i++) { int to = g[v][i].first; if (to == p) continue; if (used[to]) continue; if (sz[to] > mx_sz) { mx_sz = sz[to]; gag = to; } } if (mx_sz * 2 <= nn) return v; return find_center(gag, v); } int find_centroid(int v) { nn = 0; dfs_sz(v, -1); int center = find_center(v, -1); dfs_sz(center, -1); return center; } vector < pair<int, int> > mas; map <int, int> mp; void update(int &answ, int x) { if (answ == -1 || x < answ) { answ = x; } } void solve(int v, int p, int L, int r) { if (p != -1) { mas.push_back(make_pair(L, r)); } for (int i = 0; i < (int)g[v].size(); i++) { int to = g[v][i].first; int len = g[v][i].second; if (to == p || used[to]) continue; solve(to, v, L + len, r + 1); if (p == -1) { for (int j = 0; j < (int)mas.size(); j++) { int L = mas[j].first; int d = mas[j].second; if (L > k) continue; if (L == k) { update(answ, d); } else { if (mp.find(k - L) != mp.end()) { update(answ, d + mp[k - L]); } } } for (int j = 0; j < (int)mas.size(); j++) { int L = mas[j].first; int d = mas[j].second; if (L > k) continue; if (mp.find(L) != mp.end()) { mp[L] = min(mp[L], d); } else { mp[L] = d; } } } } } void centroid_decomposition() { queue <int> q; q.push(1); while (!q.empty()) { int v = q.front(); q.pop(); int center = find_centroid(v); mp.clear(); solve(center, -1, 0, 0); used[center] = true; for (int i = 0; i < (int)g[center].size(); i++) { int to = g[center][i].first; if (used[to]) continue; if (sz[to] == 1) continue; q.push(to); } } } int best_path(int n, int K, int h[][2], int l[]) { k = K; for (int i = 0; i < n - 1; i++) { int a = h[i][0]; int b = h[i][1]; int c = l[i]; g[a].push_back(make_pair(b, c)); g[b].push_back(make_pair(a, c)); } centroid_decomposition(); return answ; }

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

race.cpp: In function 'int find_center(int, int)':
race.cpp:55:5: warning: 'v' may be used uninitialized in this function [-Wmaybe-uninitialized]
   55 |     if (to == p) continue;
      |     ^~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...