제출 #965909

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
965909		Gromp15	자매 도시 (APIO20_swap)	C++17	13 / 100	137 ms	31084 KiB

swap

#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) {
      |  ^~~

• Subtask 1: 6 / 6
• Subtask 2: 7 / 7
• Subtask 3: 0 / 17
• Subtask 4: 0 / 20
• Subtask 5: 0 / 23
• Subtask 6: 0 / 27