Submission #104395

#TimeUsernameProblemLanguageResultExecution timeMemory
104395dfistricRace (IOI11_race)C++14
0 / 100
15 ms9984 KiB
#include <bits/stdc++.h> #include "race.h" #define FOR(i, a, b) for (int i = (a); i < (b); i++) #define REP(i, n) FOR(i, 0, n) #define ll long long using namespace std; const int MAXN = 200100; vector <pair <int, int> > ve[MAXN]; int sub[MAXN]; int bio[MAXN], cnt; int n, k; int out_len = MAXN; int len[5 * MAXN]; int date[5 * MAXN]; int num; void rek1(int x, int l, int di) { if (k >= l && date[k - l] == num) { //cout << x << " " << di + len[k - l] << endl; out_len = min(out_len, di + len[k - l]); } //cout << x << endl; //cout << l << " " << di << endl; //cout << k - l << " " << date[k - l] << endl << endl; bio[x] = cnt; for (auto tr : ve[x]) { int y = tr.first, d = tr.second; if (bio[y] >= cnt) continue; rek1(y, l + d, di + 1); } return; } void rek2(int x, int l, int di) { if (date[l] < num) { date[l] = num; len[l] = 1e9; } len[l] = min(len[l], di); bio[x] = cnt; for (auto tr : ve[x]) { int y = tr.first, d = tr.second; if (bio[y] >= cnt) continue; rek2(y, l + d, di + 1); } return; } void solve(int x) { bio[x] = 1e9; // cout << "..." << x << endl; num++; cnt++; date[0] = num, len[0] = 0; for (auto tr : ve[x]) { int y = tr.first, d = tr.second; if (bio[y] >= cnt) continue; rek1(y, d, 1); cout << endl; cnt++; rek2(y, d, 1); cnt++; } return; } int si; void dfs(int x) { si++; bio[x] = cnt; sub[x] = 1; for (auto tr : ve[x]) { int y = tr.first; if (bio[y] >= cnt) continue; dfs(y); sub[x] += sub[y]; } return; } int find_centroid(int x) { bio[x] = cnt; int ma = si - sub[x]; for (auto tr : ve[x]) { int y = tr.first; if (bio[y] >= cnt) continue; int t = find_centroid(y); if (t != -1) return y; ma = max(ma, sub[y]); } if (ma <= si / 2) return x; return -1; } void decompose(int x) { cnt++, si = 0; dfs(x); cnt++; int c = find_centroid(x); solve(c); for (auto tr : ve[c]) { int y = tr.first; if (bio[y] != 1e9) decompose(y); } return; } int best_path(int N, int K, int H[][2], int L[]) { n = N, k = K; REP(i, n) { int a = H[i][0], b = H[i][1], c = L[i]; ve[a].push_back({b, c}); ve[b].push_back({a, c}); } decompose(0); if (out_len == MAXN) return -1; return out_len; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...