제출 #396471

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
396471		Kevin_Zhang_TW	자매 도시 (APIO20_swap)	C++17	37 / 100	2088 ms	12084 KiB

swap

#include <bits/stdc++.h>
#include "swap.h"
using namespace std;
using ll = long long;
#define pb emplace_back
#define AI(i) begin(i), end(i)
template<class T> bool chmin(T &a, T b) { return b < a && (a = b, true); }
template<class T> bool chmax(T &a, T b) { return a < b && (a = b, true); }
#ifdef KEV
#define DE(args...) kout("[ " + string(#args) + " ] = ", args)
void kout() { cerr << endl; }
template<class T, class ...U> void kout(T a, U ...b) { cerr << a << ' ', kout(b...); }
template<class T> void debug(T l, T r) { while (l != r) cerr << *l << " \n"[next(l)==r], ++l; }
#else
#define DE(...) 0
#define debug(...) 0
#endif

const int MAX_N = 300010, inf = 1e9 + 7;

struct dsu {
	vector<int> g, sz, good, deg;
	dsu(int n) { 
		g.resize(n), sz.resize(n, 1), good.resize(n), deg.resize(n);
		iota(AI(g), 0); 
	}
	int F(int i) { return i == g[i] ? i : g[i] = F(g[i]); }
	void M(int a, int b) {
		++deg[a], ++deg[b];
		good[F(a)] |= deg[a] > 2;
		good[F(b)] |= deg[b] > 2;
		a = F(a), b = F(b);
		if (a == b) return good[a] = true, void();
		if (sz[a] < sz[b]) swap(a, b);
		return g[b] = a, sz[a] += sz[b], good[a] |= good[b], void();
	}
	bool qry(int a, int b) {
		return F(a) == F(b) && good[F(a)];
	}
};

int n, m;
vector<tuple<int,int,int>> alle;

void init(int N, int M,
          std::vector<int> U, std::vector<int> V, std::vector<int> W) {
	n = N, m = M;
	for (int i = 0;i < m;++i) {
		alle.pb(W[i], U[i], V[i]);
	}
	sort(AI(alle));
}

int getMinimumFuelCapacity(int X, int Y) {

	dsu D(n);

	for (auto [w, a, b] : alle) {
		D.M(a, b);
		if (D.qry(X, Y)) return w;
	}

	assert(m == n-1);

	return -1;
}

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