제출 #965909

#제출 시각아이디문제언어결과실행 시간메모리
965909Gromp15자매 도시 (APIO20_swap)C++17
13 / 100
137 ms31084 KiB
#include "swap.h" #include <bits/stdc++.h> using namespace std; #define sz(x) int(x.size()) #define all(x) x.begin(), x.end() #define db double #define ll long long #define ar array template<typename T> bool ckmin(T& a, const T& b) { return a > b ? a = b, 1 : 0; } template<typename T> bool ckmax(T& a, const T& b) { return a < b ? a = b, 1 : 0; } struct dsu { vector<vector<int>> adj; vector<int> deg, p, sub, tin, tout; vector<bool> mark; int who; dsu() {} dsu(int n, int m) : adj(n + m), deg(n), p(n + m), who(n), sub(n + m), tin(n + m), tout(n + m), mark(n + m) { iota(all(p), 0); } int get(int v) { return v == p[v] ? v : p[v] = get(p[v]); } void add(int x, int y) { int ox = x, oy = y; x = get(x), y = get(y); p[x] = who, p[y] = who; if (deg[ox] == 0) sub[who] += -1; else if (deg[ox] == 1) sub[who] += 1; if (deg[oy] == 0) sub[who] += -1; else if (deg[oy] == 1) sub[who] += 1; deg[ox]++, deg[oy]++; if (deg[ox] > 2 || deg[oy] > 2) mark[who] = 1; adj[who].emplace_back(x); if (x != y) adj[who].emplace_back(y); who++; } void process(int sx) { int timer = 0; auto dfs = [&](auto&& s, int v, int p) -> void { tin[v] = timer++; for (int u : adj[v]) if (u != p) { s(s, u, v); sub[v] += sub[u]; mark[v] = mark[v] || mark[u]; } tout[v] = timer - 1; }; dfs(dfs, sx, -1); } bool anc(int x, int y) { return tin[x] <= tin[y] && tout[y] <= tout[x]; } }; const int INF = 1e9; vector<vector<ar<int, 3>>> adj; vector<int> weights; int n, m; dsu d; void init(int N, int M, std::vector<int> U, std::vector<int> V, std::vector<int> W) { n = N, m = M; adj.resize(N + 1); d = dsu(n, m); for (int i = 0; i < M; i++) { adj[U[i]].push_back({V[i], W[i], i}); adj[V[i]].push_back({U[i], W[i], i}); } vector<int> idx(M); iota(all(idx), 0); sort(all(idx), [&](int x, int y) { return W[x] < W[y]; }); for (int i = 0; i < M; i++) { d.add(U[idx[i]], V[idx[i]]); } d.process(n + m - 1); weights.resize(m); for (int i = 0; i < m; i++) { weights[i] = W[idx[i]]; } } int getMinimumFuelCapacity(int X, int Y) { auto good = [&](int mid) -> bool { return d.anc(mid + n, X) && d.anc(mid + n, Y) && (d.mark[mid + n] || d.sub[mid + n] == 0); }; int l = 0, r = m - 1, ans = m - 1; if (!good(r)) return -1; while (l <= r) { int mid = (l+r)/2; if (good(mid)) ans = mid, r = mid-1; else l = mid+1; } return weights[ans]; }

컴파일 시 표준 에러 (stderr) 메시지

swap.cpp: In constructor 'dsu::dsu(int, int)':
swap.cpp:16:6: warning: 'dsu::who' will be initialized after [-Wreorder]
   16 |  int who;
      |      ^~~
swap.cpp:14:22: warning:   'std::vector<int> dsu::sub' [-Wreorder]
   14 |  vector<int> deg, p, sub, tin, tout;
      |                      ^~~
swap.cpp:18:2: warning:   when initialized here [-Wreorder]
   18 |  dsu(int n, int m) : adj(n + m), deg(n), p(n + m), who(n), sub(n + m), tin(n + m), tout(n + m), mark(n + m) {
      |  ^~~
#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...