Submission #57599

#	Time	Username	Problem	Language	Result	Execution time	Memory
57599		polyfish	Priglavci (COCI18_priglavci)	C++14	16 / 160	21 ms	1672 KiB

priglvaci

//I love armpit fetish

#include <bits/stdc++.h>
using namespace std;
 
#define debug(x) cerr << #x << " = " << x << '\n';
#define BP() cerr << "OK!\n";
#define PR(A, n) {cerr << #A << " = "; for (int _=1; _<=n; ++_) cerr << A[_] << ' '; cerr << '\n';}
#define PR0(A, n) {cerr << #A << " = "; for (int _=0; _<n; ++_) cerr << A[_] << ' '; cerr << '\n';}
#define FILE_NAME "data"
#define x first
#define y second

typedef pair<int, int> point;

const int MAX_N = 202;
const int INF = 1e9;

int n, m, bus_capacity, nBus, c[MAX_N][MAX_N], f[MAX_N][MAX_N];
int source, target, d[MAX_N], nTime, visited[MAX_N];
vector<int> bus[MAX_N], g[MAX_N];
point bus_stop[MAX_N], student[MAX_N];

int sqr(int x) {
	return x * x;
}

int dist(point p, point q) {
	return sqr(p.x - q.x) + sqr(p.y - q.y);
}

int dist(int bus_id, point s) {
	int res = INF;
	for (int i=0; i<bus[bus_id].size(); ++i) {
		int u = bus[bus_id][i];
		res = min(res, dist(bus_stop[u], s));
	}
	return res;
} 

void enter() {
	cin >> n >> m >> bus_capacity >> nBus;
	for (int i=1; i<=n; ++i)
		cin >> student[i].x >> student[i].y;
	for (int i=1; i<=m; ++i)
		cin >> bus_stop[i].x >> bus_stop[i].y;
	for (int i=1; i<=nBus; ++i) {
		int k; cin >> k;
		while (k--) {
			int x; cin >> x;
			bus[i].push_back(x);
		}
	}
}

void init_graph(int weakness) {
	source = 1;
	target = nBus + n + 2;
	for (int i=source; i<=target; ++i)
		g[i].clear();
	memset(c, 0, sizeof(c));
	memset(f, 0, sizeof(f));
	for (int i=2; i<=nBus+1; ++i) {
		g[source].push_back(i);
		g[i].push_back(source);
		c[source][i] = bus_capacity;
	}
	for (int i=nBus+2; i<=nBus+n+1; ++i) {
		g[target].push_back(i);
		g[i].push_back(target);
		c[i][target] = 1;
	}
	for (int i=1; i<=nBus; ++i) {
		for (int j=1; j<=n; ++j) {
			if (dist(i, student[j])<=weakness) {
				g[i+1].push_back(j+nBus+1);
				g[j+nBus+1].push_back(i+1);
				c[i+1][j+nBus+1] = 1;
			}
		}
	}
}

bool bfs() {
	memset(d, 0, sizeof(d));
	d[source] = 1;
	queue<int> qu;
	qu.push(source);
	while (qu.size()) {
		int u = qu.front();
		qu.pop();
		if (u==target)
			return true;
		for (int i=0; i<g[u].size(); ++i) {
			int v = g[u][i];
			if (d[v]==0 && c[u][v]>f[u][v]) {
				d[v] = d[u] + 1;
				qu.push(v);
			}
		}
	}
	return false;
}

int find_path(int u, int delta) {
	if (visited[u] != nTime)
		visited[u] = nTime;
	else
		return 0;
	if (u==target)
		return delta;
	for (int i=0; i<g[u].size(); ++i) {
		int v = g[u][i];
		if (d[v]==d[u] + 1 && c[u][v]>f[u][v]) {
			int x = find_path(v, min(delta, c[u][v]-f[u][v]));
			if (x>0) {
				f[u][v] += x;
				f[v][u] -= x;
				return x;
			}
		}
	}
	return 0;
}

int max_flow(int weakness) {
	init_graph(weakness);
	// PR0(g[3], g[3].size());
	// debug(c[4][5]);
	int res = 0;
	while (bfs()) {
		while (true) {
			++nTime;
			int x = find_path(source, INF);
			if (x==0)
				break;
			res += x;
			//assert(res<=n);
		}
	}
	return res;
}

int bisect() {
	int l = 0, r = INF, mid = (l + r) / 2;
	while (l!=mid && mid!=r) {
		if (max_flow(mid) == n)
			r = mid;
		else
			l = mid;
		mid = (l + r) / 2;
	}
	for (int i=l; i<=r; ++i)
		if (max_flow(i) == n)
			return i;
}

void trace() {
	for (int i=nBus+2; i<=nBus+n+1; ++i) {
		for (int j=2; j<=nBus+1; ++j) {
			if (f[j][i]==1) {
				cout << j-1 << '\n';
				break;
			}
		}
	}
}

int main() {
	//#define OFFLINE_JUDGE doraemon
	#ifdef OFFLINE_JUDGE
		freopen(FILE_NAME".inp", "r", stdin);
		freopen(FILE_NAME".out", "w", stdout);
	#endif
	ios::sync_with_stdio(0); cin.tie(0);
	enter();
	if (bus_capacity * nBus < n) {
		cout << -1;
		return 0;
	}
	//debug(max_flow(4));
	cout << bisect() << '\n';
	trace();
}

Compilation message (stderr)

priglvaci.cpp: In function 'int dist(int, point)':
priglvaci.cpp:34:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i=0; i<bus[bus_id].size(); ++i) {
                ~^~~~~~~~~~~~~~~~~~~
priglvaci.cpp: In function 'bool bfs()':
priglvaci.cpp:94:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int i=0; i<g[u].size(); ++i) {
                 ~^~~~~~~~~~~~
priglvaci.cpp: In function 'int find_path(int, int)':
priglvaci.cpp:112:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i=0; i<g[u].size(); ++i) {
                ~^~~~~~~~~~~~
priglvaci.cpp: In function 'int bisect()':
priglvaci.cpp:156:1: warning: control reaches end of non-void function [-Wreturn-type]
 }
 ^

• Subtask 1: 16 / 160