Submission #222196

#	Time	Username	Problem	Language	Result	Execution time	Memory
222196		ZwariowanyMarcin	Priglavci (COCI18_priglavci)	C++17	160 / 160	22 ms	5888 KiB

priglvaci

#include <bits/stdc++.h>
#define ll long long
#define ld long double
#define pb push_back
#define mp make_pair
#define ss(x) (int) x.size()
#define fi first
#define se second
#define cat(x) cerr << #x << " = " << x << endl
#define rep(i, j, n) for (int i = j; i <= n; ++i)
#define per(i, j, n) for (int i = n; j <= i; --i)
#define all(x) x.begin(), x.end()
 
using namespace std;

const int nax = 1e5 + 10;

struct matching {
	vector <int> g[nax];
	int t[nax];
	int color[nax];
	int q[nax];
	int c;
	
	void add(int a, int b) {
		g[a].pb(b);
	}
	
	bool dfs(int v) {
		color[v] = c;
		for (auto it : g[v]) {
			if (t[it] == -1) {
				t[it] = v;
				q[v] = it;
				return true;
			}
		}
		for (auto it : g[v]) {
			if (color[t[it]] != c && dfs(t[it]) == true) {
				t[it] = v;
				q[v] = it;
				return true;
			}
		}
		return false;
	}
	
	bool perfect(int n, int m) { // lewo, prawo
		rep(i, 0, m - 1) t[i] = -1;
		rep(i, 0, n - 1) color[i] = -1;
		c = 0;
		int ans = 0;
		rep(i, 0, n - 1) {
			ans += dfs(i);
			c++;
		}
		return ans == n;
	}
	
	void reset(int n) {
		rep(i, 0, n - 1) g[i].clear();
	}
} ja;

struct pt {
	int x, y;
};
		
int n, m, c, k;
pt s[nax];
pt t[nax];
vector <int> f[nax];
	
int odl(int a, int b) {
	return (s[a].x - t[b].x) * (s[a].x - t[b].x) + (s[a].y - t[b].y) * (s[a].y - t[b].y);
}	
	
bool ok(int dis) {
	ja.reset(n);
	rep(i, 0, n - 1) {
		rep(j, 0, k - 1) {
			for (auto it : f[j])
				if (odl(i, it) <= dis) {
					rep(s, j * c, (j + 1) * c - 1) {
						ja.add(i, s);
					}
					break;
				}
		}
	}
	return ja.perfect(n, c * k);
}
	
	

int main() {		
	scanf ("%d%d%d%d", &n, &m, &c, &k);
	rep(i, 0, n - 1) scanf ("%d%d", &s[i].x, &s[i].y);
	rep(i, 0, m - 1) scanf ("%d%d", &t[i].x, &t[i].y);
	rep(i, 0, k - 1) {
		int e;
		scanf ("%d", &e);
		while (e--) {
			int r;
			scanf ("%d", &r);
			r--;
			f[i].pb(r);
		}
	} 
	int l = 0, r = 1e9;
	while (l < r) {
		int m = (l + r) / 2;
		if (ok(m)) r = m;
		else l = m + 1;
	}
	ok(l);
	if (l == 1e9) return printf ("-1\n"), 0;
	printf ("%d\n", l);
	rep(i, 0, n - 1) {
		for (auto it : f[ja.q[i] / c])
			if (odl(i, it) <= l) {
				printf ("%d\n", it + 1);
				break;
			}
	}
	
	return 0;
}

Compilation message (stderr)

priglvaci.cpp: In function 'int main()':
priglvaci.cpp:97:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf ("%d%d%d%d", &n, &m, &c, &k);
  ~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
priglvaci.cpp:98:25: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  rep(i, 0, n - 1) scanf ("%d%d", &s[i].x, &s[i].y);
                   ~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
priglvaci.cpp:99:25: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  rep(i, 0, m - 1) scanf ("%d%d", &t[i].x, &t[i].y);
                   ~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
priglvaci.cpp:102:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf ("%d", &e);
   ~~~~~~^~~~~~~~~~
priglvaci.cpp:105:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    scanf ("%d", &r);
    ~~~~~~^~~~~~~~~~

• Subtask 1: 160 / 160