Submission #595378

#	Time	Username	Problem	Language	Result	Execution time	Memory
595378		Zanite	Priglavci (COCI18_priglavci)	C++17	96 / 160	22 ms	2004 KiB

priglvaci

#include <bits/stdc++.h>
using namespace std;

using ll	= long long;
using pll	= pair<ll, ll>;

#define fi		first
#define se		second
#define sqr(x)	((x)*(x))

const ll INF	= 1e18;

struct MaximumFlow {
	// Implementation of the Edmonds-Karp algorithm.

	ll n, _INF_FLOW;
	vector<vector<ll>> capacity, flow, dir;
	vector<vector<ll>> adj;

	MaximumFlow(ll n) : n(n), _INF_FLOW(INF) {
		vector<vector<ll>> _tmp = vector<vector<ll>>(n+1, vector<ll>(n+1));
		capacity = flow = dir = _tmp;

		adj.assign(n+1, vector<ll>(0));
	}

	void addEdge(ll u, ll v, ll cap) {
		//cout << u << ' ' << v << ' ' << cap << '\n';

		// adds a directed edge u -> v with capacity cap
		dir[u][v] = 1, dir[v][u] = -1;
		capacity[u][v] += cap;
		
		adj[u].push_back(v);
		adj[v].push_back(u);
	}

	ll bfs(ll source, ll sink, vector<ll> &parent) {
		parent.assign(n+1, -1);
		parent[source] = -2;

		queue<pll> Q;
		Q.push({source, _INF_FLOW});

		while (!Q.empty()) {
			ll cur, flow;
			tie(cur, flow) = Q.front();
			Q.pop();

			for (auto &nxt : adj[cur]) {
				if (parent[nxt] == -1 && capacity[cur][nxt]) {
					parent[nxt] = cur;
					ll newFlow = min(flow, capacity[cur][nxt]);

					if (nxt == sink) {return newFlow;}
					Q.push({nxt, newFlow});
				}
			}
		}

		return 0;
	}

	ll computeMaxflow(ll source, ll sink) {
		// computes the value of the maximum flow
		// the flow through each edge is stored in flow[][]

		// precaution when there are multiple edges
		for (ll i = 0; i <= n; i++) {
			sort(adj[i].begin(), adj[i].end());
			adj[i].erase(unique(adj[i].begin(), adj[i].end()), adj[i].end());
		}

		ll maxFlow = 0, newFlow;
		vector<ll> parent(n+1);

		while (newFlow = bfs(source, sink, parent)) {
			maxFlow += newFlow;
			ll cur = sink;
			while (cur != source) {
				ll prv = parent[cur];

				capacity[prv][cur] -= newFlow;
				capacity[cur][prv] += newFlow;

				flow[prv][cur] += dir[prv][cur] * newFlow;
				flow[cur][prv] += dir[cur][prv] * newFlow;

				cur = prv;
			}
		}

		return maxFlow;
	}
};

const int maxN	= 101;

ll N, M, C, K;
vector<pll> student(1), bus(1);
vector<ll> routes[maxN];

inline ll dist(const pll &a, const pll &b) {
	return (sqr(a.fi - b.fi) + sqr(a.se - b.se));
}

int main() {
	scanf("%lld %lld %lld %lld", &N, &M, &C, &K);
	for (ll x, y, i = 1; i <= N; i++) {
		scanf("%lld %lld", &x, &y);
		student.push_back({x, y});
	}
	for (ll x, y, i = 1; i <= M; i++) {
		scanf("%lld %lld", &x, &y);
		bus.push_back({x, y});
	}
	for (ll k, i = 1; i <= K; i++) {
		scanf("%lld", &k);
		for (ll st = 1; st <= k; st++) {
			scanf("%lld", &st);
			routes[i].push_back(st);
		}
	}

	ll L = 0, R = 4'000'000, ans = -1;
	vector<vector<ll>> backtrack;

	const ll _source = 1, _sink = 2;
	#define STUDENT(x)	(x)+2
	#define ROUTE(x)	(x)+N+2

	while (L <= R) {
		ll M = (L + R) >> 1;
		//cout << M << '\n';

		MaximumFlow F(N+K+2);

		for (ll s = 1; s <= N; s++) {
			F.addEdge(_source, STUDENT(s), 1);
		}
		for (ll r = 1; r <= K; r++) {
			F.addEdge(ROUTE(r), _sink, C);
		}

		for (ll s = 1; s <= N; s++) {
			for (ll r = 1; r <= K; r++) {
				for (auto &b : routes[r]) {
					if (dist(student[s], bus[b]) <= M) {
						F.addEdge(STUDENT(s), ROUTE(r), 1);
						break;
					}
				}
			}
		}

		ll flow = F.computeMaxflow(_source, _sink);

		if (flow != N) {
			L = M + 1;
		} else {
			R = M - 1;
			ans = M;
			backtrack = F.flow;
		}
	}

	printf("%lld\n", ans);

	if (ans != -1) {
		for (ll s = 1; s <= N; s++) {
			for (ll r = 1; r <= K; r++) {
				if (backtrack[STUDENT(s)][ROUTE(r)] == 1) {
					for (auto &b : routes[r]) {
						if (dist(student[s], bus[b]) <= ans) {
							printf("%lld\n", b);
							break;
						}
					}
				}
			}
		}
	}
}

Compilation message (stderr)

priglvaci.cpp: In member function 'll MaximumFlow::computeMaxflow(ll, ll)':
priglvaci.cpp:77:18: warning: suggest parentheses around assignment used as truth value [-Wparentheses]
   77 |   while (newFlow = bfs(source, sink, parent)) {
      |          ~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
priglvaci.cpp: In function 'int main()':
priglvaci.cpp:108:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  108 |  scanf("%lld %lld %lld %lld", &N, &M, &C, &K);
      |  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
priglvaci.cpp:110:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  110 |   scanf("%lld %lld", &x, &y);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~
priglvaci.cpp:114:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  114 |   scanf("%lld %lld", &x, &y);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~
priglvaci.cpp:118:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  118 |   scanf("%lld", &k);
      |   ~~~~~^~~~~~~~~~~~
priglvaci.cpp:120:9: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  120 |    scanf("%lld", &st);
      |    ~~~~~^~~~~~~~~~~~~

• Subtask 1: 96 / 160