Submission #151636

#TimeUsernameProblemLanguageResultExecution timeMemory
151636kuroniTrip to the Galapagos Islands (FXCUP4_island)C++17
100 / 100
3380 ms32844 KiB
#include "island.h" #include <bits/stdc++.h> #define fi first #define se second using namespace std; const int N = 100005; int m, dsu[N]; map<pair<int, int>, int> ma; vector<int> col[N]; vector<pair<int, int>> ele[N], com[N]; int trace(int u) { return dsu[u] < 0 ? u : dsu[u] = trace(dsu[u]); } void connect(int u, int v, int ind) { if ((u = trace(u)) == (v = trace(v))) return; if (dsu[u] > dsu[v]) swap(u, v); dsu[u] += dsu[v]; dsu[v] = u; for (pair<int, int> &tmp : ele[v]) { int cur = tmp.fi; ele[u].push_back({cur, ind}); com[cur].push_back({u, ind}); } } void Init(int k, std::vector<int> f, std::vector<int> s, std::vector<int> e) { int n = f.size(); for (int i = 0; i < n; i++) { dsu[i] = -1; col[f[i]].push_back(i); ele[i].push_back({i, -1}); com[i].push_back({i, -1}); } m = s.size(); for (int i = 0; i < m; i++) { int u = s[m - 1 - i], v = e[m - 1 - i]; connect(u, v, i); } for (int i = 0; i < n; i++) { for (pair<int, int> &v : ele[i]) v.fi = f[v.fi]; sort(ele[i].begin(), ele[i].end()); } } int Separate(int u, int v) { if (col[u].size() > col[v].size() || (col[u].size() == col[v].size() && u > v)) swap(u, v); if (ma.count({u, v}) > 0) return ma[{u, v}]; int ans = m + 1; for (int &x : col[u]) { int le = 0, ri = com[x].size(); while (le <= ri) { int mi = (le + ri) / 2; int cur = com[x][mi].fi; auto it = lower_bound(ele[cur].begin(), ele[cur].end(), make_pair(v, -1)); if (it == ele[cur].end() || it->fi != v) le = mi + 1; else { ans = min(ans, max(com[x][mi].se, it->se)); ri = mi - 1; } } } return ma[{u, v}] = m - ans; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...