제출 #927308

#제출 시각아이디문제언어결과실행 시간메모리
927308TAhmed33자매 도시 (APIO20_swap)C++17
53 / 100
298 ms36268 KiB
#include <bits/stdc++.h> using namespace std; const int MAXN = 1e5 + 25; int t[MAXN], n, m; array <int, 3> edges[MAXN]; int deg[MAXN]; vector <int> sub[MAXN]; int par[MAXN]; bool ok[MAXN]; vector <array <int, 3>> times[MAXN]; int sum = 0; void init (int N, int M, vector <int> u, vector <int> v, vector <int> w) { n = N; m = M; for (int i = 0; i < m; i++) edges[i] = {u[i], v[i], w[i]}; for (int i = 0; i < m; i++) t[i] = i; sort(t, t + m, [&] (int &x, int &y) { return edges[x][2] < edges[y][2]; }); for (int i = 0; i < n; i++) { sub[i].push_back(i); par[i] = i; times[i].push_back({-1, i, 0}); sum++;assert(sum <= 1e7); } for (int i = 0; i < m; i++) { int a = edges[t[i]][0], b = edges[t[i]][1]; if (par[a] == par[b]) { if (ok[par[a]]) { deg[a]++; deg[b]++; continue; } ok[par[a]] = 1; for (auto j : sub[par[a]]) { times[j].push_back({i, par[a], 1}); sum++;assert(sum <= 1e7); } deg[a]++; deg[b]++; continue; } if (sub[par[a]].size() > sub[par[b]].size()) swap(a, b); bool flag = ok[par[a]] || ok[par[b]]; flag |= deg[a] > 1 || deg[b] > 1; if (!flag) { int l = par[a]; for (auto j : sub[l]) { times[j].push_back({i, par[b], 0}); sum++;assert(sum <= 1e7); par[j] = par[b]; sub[par[b]].push_back(j); } sub[l].clear(); deg[a]++; deg[b]++; continue; } if (!ok[par[b]]) { ok[par[b]] = 1; for (auto j : sub[par[b]]) { times[j].push_back({i, par[b], 1}); sum++; assert(sum <= 1e7); } } int l = par[a]; for (auto j : sub[l]) { times[j].push_back({i, par[b], 1}); sum++;assert(sum <= 1e7); par[j] = par[b]; sub[par[b]].push_back(j); } sub[l].clear(); deg[a]++; deg[b]++; } } int getMinimumFuelCapacity (int x, int y) { int l = 0, r = m - 1, ans = -1; while (l <= r) { int mid = (l + r) / 2; array <int, 3> ff = {mid + 1, (int)-1e9, (int)-1e9}; auto g = lower_bound(times[x].begin(), times[x].end(), ff) - times[x].begin(); auto h = lower_bound(times[y].begin(), times[y].end(), ff) - times[y].begin(); g--; h--; if (times[x][g][1] != times[y][h][1]) { l = mid + 1; continue; } if (!times[x][g][2] || !times[y][h][2]) { l = mid + 1; } else { r = mid - 1; ans = mid; } } return ans == -1 ? -1 : edges[t[ans]][2]; }
#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...