제출 #1275829

#제출 시각아이디문제언어결과실행 시간메모리
1275829nanj0178Race (IOI11_race)C++20
0 / 100
2 ms332 KiB
#include <bitset> #include<iostream> #include<vector> #include<array> #include<algorithm> #include<set> #include<cmath> #include<unordered_map> #include<iomanip> #include <map> #include <queue> #include <stack> #include <cstring> #include <climits> #include <chrono> #include <random> #include <cassert> using namespace std; #define PRINTARRAY(st, en, a) for(int _i = st; _i <= en; _i++) {cout << a[_i] << (_i != en ? " " : "\n");} #define SZ(A) (int)A.size() using LL = long long; mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); vector<vector<array<LL,2>>> E; vector<int> dep; vector<LL> path; vector<int> tin; vector<int> tout; vector<int> dfsOrderV; vector<int> heavyChild; vector<int> groupSize; vector<int> heavyParent; int dfsOrder; void dfs(int cur, int pre, int d, LL p) { dfsOrder++; tin[cur] = dfsOrder; dfsOrderV[dfsOrder] = cur; path[cur] = p; dep[cur] = d; int subGroupMax = 0; int heavyChildId = -1; for(auto [next, w] : E[cur]) { if (pre == next) continue; dfs(next, cur, d + 1, p + w); groupSize[cur] += groupSize[next]; if (groupSize[next] > subGroupMax) { subGroupMax = groupSize[next]; heavyChildId = next; } } if (heavyChildId != -1) { heavyChild[cur] = heavyChildId; heavyParent[heavyChildId] = cur; } tout[cur] = dfsOrder; } int best_path(int N, int K, int H[][2], int L[]) { E.assign(N + 1, {}); dep.assign(N + 1, 0); path.assign(N + 1, 0); dfsOrderV.assign(N + 1, 0); tin.assign(N + 1, 0); tout.assign(N + 1, 0); heavyChild.assign(N + 1, -1); groupSize.assign(N + 1, 1); heavyParent.assign(N + 1, -1); for(int i = 0; i < N; i++) { int x = H[i][0]; int y = H[i][1]; int w = L[i]; E[x].push_back({y, w}); E[y].push_back({x, w}); } dfsOrder = 0; dfs(0, 0, 1, 0); // cout << "FIN" << endl; // PRINTARRAY(0, N - 1, path); // PRINTARRAY(0, N - 1, tin); // PRINTARRAY(0, N - 1, tout); // PRINTARRAY(0, N - 1, heavyChild); auto add = [&](int x, map<LL, int> &m) { if (m.count(path[x])) { m[path[x]] = min(m[path[x]], dep[x]); } else { m[path[x]] = dep[x]; } }; int ans = N; auto check = [&](int cur, int root, map<LL, int> &m) { if (cur == -1) return; LL need = K + 2 * path[root] - path[cur]; if (m.count(need)) { // cout << cur << " " << root << " " << need << " " << m[need] + dep[cur] - 2 * dep[root] << endl; ans = min(ans, m[need] + dep[cur] - 2 * dep[root]); } }; auto dfs1 = [&](auto &&self, int cur, int pre, int root, map<LL, int> &m) -> void { LL need = K + 2 * path[root] - path[cur]; if (m.count(need)) { ans = min(ans, m[need] + dep[cur] - 2 * dep[root]); } for(auto [next, _] : E[cur]) { if (next == pre) continue; self(self, next, cur, root, m); } }; auto dfs2 = [&](auto &&self, int cur, int pre, int root, map<LL, int> &m)-> void { add(cur, m); for(auto [next, _] : E[cur]) { if (next == pre) continue; self(self, next, cur, root, m); } }; for(int i = 0; i < N; i++) { if (groupSize[i] != 1) continue; // cout << "----------" << endl; // cout << "st:" << i <<endl; // start on leaf map<LL, int> mPath; int cur = i; while(cur != -1) { add(cur, mPath); int child = heavyChild[cur]; for(auto [next, _]: E[cur]) { if (next == child) continue; dfs1(dfs1, next, cur, cur, mPath); dfs2(dfs2, next, cur, cur, mPath); } // if (child != -1) { // // cout << cur << " check "; // // for(int i = tin[cur] + 1; i < tin[child]; i++) cout << dfsOrderV[i] << " "; // // for(int i = tout[child] + 1; i <= tout[cur]; i++) cout << dfsOrderV[i] << " "; // // cout << endl; // for(int i = tin[cur]; i < tin[child]; i++) check(dfsOrderV[i], cur, mPath); // for(int i = tout[child] + 1; i <= tout[cur]; i++) check(dfsOrderV[i], cur, mPath); // for(int i = tin[cur]; i < tin[child]; i++) add(dfsOrderV[i], mPath); // for(int i = tout[child] + 1; i <= tout[cur]; i++) add(dfsOrderV[i], mPath); // } // cout << cur << " check " << child << endl;; // check(cur, cur, mPath); cur = heavyParent[cur]; } } if (ans == N) { return -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...