#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
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);
~~~~~~^~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
8 ms |
5120 KB |
Output is correct |
| 2 |
Correct |
8 ms |
5120 KB |
Output is correct |
| 3 |
Correct |
18 ms |
5112 KB |
Output is correct |
| 4 |
Correct |
9 ms |
5120 KB |
Output is correct |
| 5 |
Correct |
9 ms |
5120 KB |
Output is correct |
| 6 |
Correct |
13 ms |
5248 KB |
Output is correct |
| 7 |
Correct |
9 ms |
5120 KB |
Output is correct |
| 8 |
Correct |
9 ms |
5120 KB |
Output is correct |
| 9 |
Correct |
22 ms |
5888 KB |
Output is correct |
| 10 |
Correct |
12 ms |
5248 KB |
Output is correct |
