Submission #1201401

#TimeUsernameProblemLanguageResultExecution timeMemory
1201401aykhn자매 도시 (APIO20_swap)C++20
100 / 100
1054 ms49208 KiB
#include "swap.h" #include <bits/stdc++.h> using namespace std; #define inf 0x3F3F3F3F const int MXN = 1e5 + 5; vector<array<int, 2>> e[MXN]; vector<array<int, 2>> cnt[4][MXN]; int val(vector<array<int, 2>> &v, int t) { return (*prev(upper_bound(v.begin(), v.end(), array<int, 2>{t, inf})))[1]; } int get(int x, int t) { int p = val(e[x], t); if (p < 0) return x; return get(p, t); } void inc(int x, int d, int t) { if (d >= 3) return; x = get(x, t); cnt[d][x].push_back({t, val(cnt[d][x], t) - 1}); cnt[d + 1][x].push_back({t, val(cnt[d + 1][x], t) + 1}); } void unite(int x, int y, int t) { x = get(x, t), y = get(y, t); if (x == y) return; if (val(e[x], t) > val(e[y], t)) swap(x, y); e[x][0][1] += e[y][0][1]; e[y].push_back({t, x}); for (int i = 0; i < 4; i++) { cnt[i][x].push_back({t, val(cnt[i][x], t) + val(cnt[i][y], t)}); } } void init(int N, int M, vector<int> U, vector<int> V, vector<int> W) { for (int i = 0; i < N; i++) { e[i] = {{-inf, -1}}; for (int j = 0; j < 4; j++) cnt[j][i] = {{-inf, 0}}; cnt[0][i][0][1] = 1; } vector<array<int, 3>> ed; for (int i = 0; i < U.size(); i++) ed.push_back({W[i], U[i], V[i]}); sort(ed.begin(), ed.end()); vector<int> deg(N, 0); for (auto &[t, u, v] : ed) { unite(u, v, t); inc(u, deg[u]++, t); inc(v, deg[v]++, t); } } int getMinimumFuelCapacity(int X, int Y) { int l = 0, r = inf; while (l < r) { int mid = (l + r) >> 1; if (get(X, mid) != get(Y, mid)) { l = mid + 1; continue; } int R = get(X, mid); if (val(cnt[1][R], mid) != 2 || val(cnt[3][R], mid)) r = mid; else l = mid + 1; } return (l == inf ? -1 : l); }
#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...