Submission #1206194

#TimeUsernameProblemLanguageResultExecution timeMemory
1206194TriseedotCat Exercise (JOI23_ho_t4)C++20
100 / 100
248 ms67768 KiB
// Made by ordinary newbie #pragma region setup #include <bits/stdc++.h> #include <random> #include <chrono> using namespace std; // variables #define int long long using ld = long double; using ll = long long; using ull = unsigned long long; template<typename T> using min_heap = priority_queue<T, vector<T>, greater<T>>; // bitwise operations #define cnt_bit(n) __builtin_popcountll(n) #define low_bit(n) ((n) & (-(n))) #define bit(n, i) (((n) >> (i)) & 1) #define set_bit(n, i) ((n) | (1ll << (i))) #define reset_bit(n, i) ((n) & ~(1ll << (i))) #define flip_bit(n, i) ((n) ^ (1ll << (i))) // math #define sqr(n) ((n) * (n)) int log2_floor(ull n) { return n ? __builtin_clzll(1) - __builtin_clzll(n) : -1; } const ll INF = 1e18; // utils #define len(x) (int) x.size() #define all(a) a.begin(), a.end() #define rall(a) a.rbegin(), a.rend() template <typename T> istream& operator>>(istream& is, vector<T>& v) { for(auto& el : v) { is >> el; } return is; } template <typename T> ostream& operator<<(ostream& os, const vector<T>& v) { for (int i = 0; i < len(v); i++) { if (i) os << ' '; os << v[i]; } return os; } template<class... Args> auto create(size_t n, Args&&... args) { if constexpr(sizeof...(args) == 1) { return vector(n, args...); } else { return vector(n, create(args...)); } } struct custom_hash { static uint64_t splitmix64(uint64_t x) { x += 0x9e3779b97f4a7c15; x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9; x = (x ^ (x >> 27)) * 0x94d049bb133111eb; return x ^ (x >> 31); } size_t operator()(uint64_t x) const { static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count(); return splitmix64(x + FIXED_RANDOM); } size_t operator()(pair<int, int> x) const { static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count(); return splitmix64(x.first + FIXED_RANDOM) ^ splitmix64(x.second + FIXED_RANDOM); } }; template<typename T, typename U> bool chmin(T& a, const U b) { if (b < a) { a = b; return true; } return false; } template<typename T, typename U> bool chmax(T& a, const U b) { if (b > a) { a = b; return true; } return false; } template<typename T> void compress(vector<T>& v) { int n = len(v); vector<pair<T, int>> u(n); for (int i = 0; i < n; i++) { u[i] = {v[i], i}; } sort(all(u)); int curr = 0; for (int i = 0; i < n; i++) { if (i != 0 && u[i].first != u[i - 1].first) curr++; v[u[i].second] = curr; } } mt19937 rng(chrono::high_resolution_clock::now().time_since_epoch().count()); #pragma endregion struct DSU { int n; vector<int> p; DSU(int N) { n = N; p.resize(n); iota(all(p), 0); } int get(int v) { if (p[v] == v) return v; return p[v] = get(p[v]); } bool unite(int v, int u) { v = get(v), u = get(u); if (v == u) return false; p[v] = u; return true; } }; const int L = 20; void solve() { int n; cin >> n; vector<int> p(n); cin >> p; vector<int> pi(n); for (int i = 0; i < n; i++) { pi[p[i] - 1] = i; } vector<vector<int>> g(n); for (int i = 0; i < n - 1; i++) { int v, u; cin >> v >> u; v--, u--; g[v].push_back(u); g[u].push_back(v); } vector<int> tin(n), tout(n), depth(n, 0); vector binup = create(n, L, 0); int timer = 0; function<void(int, int)> dfs = [&] (int v, int pr) { binup[v][0] = pr; for (int i = 1; i < L; i++) { binup[v][i] = binup[binup[v][i - 1]][i - 1]; } tin[v] = timer++; for (int u : g[v]) { if (u == pr) continue; depth[u] = depth[v] + 1; dfs(u, v); } tout[v] = timer; }; dfs(0, 0); auto is_pr = [&] (int pr, int v) { return tin[pr] <= tin[v] && tout[v] <= tout[pr]; }; auto dist = [&] (int v, int u) { int w = v; for (int i = L - 1; i >= 0; i--) { if (!is_pr(binup[w][i], u)) { w = binup[w][i]; } } if (!is_pr(w, u)) { w = binup[w][0]; } return depth[v] + depth[u] - 2 * depth[w]; }; vector<int> dp(n, -1); DSU dsu(n); for (int v : pi) { dp[v] = 0; for (int u : g[v]) { if (dp[u] == -1) continue; u = dsu.get(u); chmax(dp[v], dp[u] + dist(v, u)); dsu.unite(u, v); } } cout << dp[pi.back()] << '\n'; } signed main() { ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0); int tt = 1; //cin >> tt; for (int i = 1; i <= tt; i++) { solve(); } }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...