Submission #200148

#	Time	Username	Problem	Language	Result	Execution time	Memory
200148		Saboon	Priglavci (COCI18_priglavci)	C++14	160 / 160	13 ms	632 KiB

priglvaci

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

const int maxn = 100 + 37;
const int maxm = 2e4 + 36;

struct point{
	int x;
	int y;
	point(int x_ = 0, int y_ = 0){
		x = x_, y = y_;
	}
}u[maxn], s[maxn];

int n, m, c, k;
bitset<maxn> bs[maxn];

int to[maxm], cap[maxm], pre[maxm], last[maxm], pos[maxm];
int cnt = 0;

int dis[2 * maxn];
int dfs(int src, int snk, int untilnow){
	if (src == snk or untilnow == 0)
		return untilnow;
//	cout << "# " << src << " " << untilnow << endl;
	int now = 0;
	for (int &ed = pos[src]; ed != -1; ed = pre[ed]){
		int u = to[ed];
		if (cap[ed] == 0 or dis[u] != dis[src] + 1)
			continue;
		int tmp = dfs(u, snk, min(cap[ed], untilnow));
		cap[ed] -= tmp, cap[ed^1] += tmp;
		untilnow -= tmp, now += tmp;
	}
	return now;
}

int Q[2 * maxn];
bool bfs(int src, int snk){
	int st = 0, en = 0;
	Q[en ++] = src;
	memset(dis, -1, sizeof dis);
	dis[src] = 0;
	while (st < en){
		int v = Q[st ++];
		for (int ed = last[v]; ed != -1; ed = pre[ed]){
			int u = to[ed];
			if (dis[u] == -1 and cap[ed]){
				dis[u] = dis[v] + 1;
				Q[en ++] = u;
			}
		}
	}
	return dis[snk] != -1;
}

int max_flow(){
	int src = n + k, snk = n + k + 1;
	int ret = 0;
	while (bfs(src, snk)){
		for (int i = 0; i <= snk; i++)
			pos[i] = last[i];		
		ret += dfs(src, snk, 110);
	}
	return ret;
}

void add_edge(int v, int u, int c){
	to[cnt] = u, cap[cnt] = c, pre[cnt] = last[v], last[v] = cnt ++;
	to[cnt] = v, cap[cnt] = 0, pre[cnt] = last[u], last[u] = cnt ++;
}

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

int dist(point a, point b){
	return sq(a.x - b.x) + sq(a.y - b.y);
}

bool check(int x){
	cnt = 0;
	memset(last, -1, sizeof last);
	int src = n + k, snk = n + k + 1;
	for (int i = 0; i < n; i++)
		add_edge(src, i, 1);
	for (int i = 0; i < k; i++)
		add_edge(i+n, snk, c);
	for (int i = 0; i < n; i++){
		bitset<maxn> near;
		for (int j = 0; j < m; j++)
			if (dist(u[i], s[j]) <= x)
				near |= bs[j];
		for (int j = 0; j < k; j++)
			if (near[j])
				add_edge(i, j+n, 1);
	}
	return (max_flow() == n);
}

int main(){
	ios_base::sync_with_stdio(false);
	cin >> n >> m >> c >> k;
	for (int i = 0; i < n; i++)
		cin >> u[i].x >> u[i].y;
	for (int i = 0; i < m; i++)
		cin >> s[i].x >> s[i].y;
	for (int i = 0; i < k; i++){
		int x;
		cin >> x;
		while (x --){
			int sta;
			cin >> sta;
			sta --;
			bs[sta][i] = 1;
		}	
	}
	int lo = -1, hi = 1e9;
	while (hi - lo > 1){
		int mid = (lo + hi) >> 1;
		if (!check(mid))
			lo = mid;
		else
			hi = mid;
	}
	if (hi == 1e9)
		return cout << -1 << '\n', 0;
	check(hi);
	cout << hi << '\n';
	int src = n + k;
	for (int i = 0; i < n; i++){
		int can;
		for (int ed = last[i]; ed != -1; ed = pre[ed]){
			int u = to[ed], c = cap[ed];
			if (u != src and c == 0)
				can = u - n;
		}
		for (int j = 0; j < m; j++){
			if (!bs[j][can] or dist(u[i], s[j]) > hi)
				continue;
			cout << j + 1 << '\n';
			break;
		}
	}
}

Compilation message (stderr)

priglvaci.cpp: In function 'int main()':
priglvaci.cpp:133:7: warning: 'can' may be used uninitialized in this function [-Wmaybe-uninitialized]
   int can;
       ^~~

• Subtask 1: 160 / 160