#include <cstdio>
#include <cassert>
#include <queue>
#include <algorithm>
#define let const auto
#define rep(name,beg,end) for(auto lim_##name = end,name = beg;name <= lim_##name;name++)
#define per(name,beg,end) for(auto lim_##name = end,name = beg;name >= lim_##name;name--)
#define repn(lim) for(auto REPN_lIM = lim,REPN = 1;REPN <= REPN_lIM;REPN++)
#define debug(...) fprintf(stderr,__VA_ARGS__)
#define trace() debug("line : %d, Function : %s\n",__LINE__,__FUNCTION__)
constexpr int maxn = 333,inf = 0x3f3f3f3f;
constexpr int sq(const int x){return x * x;}
int n,m,c,k;
namespace dinic{
constexpr int maxn = 333,maxm = 5e5;
struct Edge{
int v,cap;
}edges[maxm];
int head[maxn],nxt[maxm],tot = 1;
void addedge(const int u,const int v,const int cap){
edges[++tot] = Edge{v,cap};
nxt[tot] = head[u];
head[u] = tot;
edges[++tot] = Edge{u,0};
nxt[tot] = head[v];
head[v] = tot;
}
void clear(){
tot = 1;
std::fill_n(head + 1,n + k + 2,0);
}
int d[maxn];
bool bfs(const int s,const int t){
static std::queue<int> q;
std::fill_n(d + 1,t,-1);
q.push(s); d[s] = 0;
while(!q.empty()){
let u = q.front(); q.pop();
for(int i = head[u];i;i = nxt[i]){
let &e = edges[i];
if(e.cap && d[e.v] == -1){
d[e.v] = d[u] + 1;
q.push(e.v);
}
}
}
return d[t] != -1;
}
int cur[maxn];
int dfs(const int u,const int t,int a){
if(u == t || !a)return a;
int res = 0,f;
for(int &i = cur[u];i;i = nxt[i]){
let &e = edges[i];
if(d[u] + 1 == d[e.v] && (f = dfs(e.v,t,std::min(a,e.cap)))){
edges[i].cap -= f;
edges[i ^ 1].cap += f;
a -= f;
res += f;
if(!a)break;
}
}
return res;
}
int maxflow(const int s,const int t){
int res = 0;
while(bfs(s,t)){
std::copy_n(head + 1,t,cur + 1);
res += dfs(s,t,0x3f3f3f3f);
}
return res;
}
}
struct Point{
int x,y;
}pa[maxn],pb[maxn];
constexpr int sqdis(const Point a,const Point b){return sq(a.x - b.x) + sq(a.y - b.y);};
int dis[maxn][maxn];
std::vector<int> line[maxn];
bool chk(const int mid){
let ss = n + k + 1,tt = ss + 1;
dinic::clear();
rep(i,1,n)
dinic::addedge(ss,i,1);
rep(i,1,k)
dinic::addedge(n + i,tt,c);
rep(i,1,n)
rep(j,1,k)
if(dis[i][j] <= mid)
dinic::addedge(i,n + j,1);
return dinic::maxflow(ss,tt) == n;
}
void getans(const int mid){
let ss = n + k + 1,tt = ss + 1;
dinic::clear();
rep(i,1,n)
dinic::addedge(ss,i,1);
rep(i,1,k)
dinic::addedge(n + i,tt,c);
rep(i,1,n)
rep(j,1,k)
if(dis[i][j] <= mid)
dinic::addedge(i,n + j,1);
dinic::maxflow(ss,tt);
rep(u,1,n){
for(int i = dinic::head[u];i;i = dinic::nxt[i]){
let &e = dinic::edges[i];
if(!e.cap && e.v >= n + 1 && e.v <= n + k){
for(let x : line[e.v - n]){
if(sqdis(pa[u],pb[x]) <= mid){
std::printf("%d\n",x);
break;
}
}
break;
}
}
}
}
int main(){
std::scanf("%d %d %d %d",&n,&m,&c,&k);
rep(i,1,n)std::scanf("%d %d",&pa[i].x,&pa[i].y);
rep(i,1,m)std::scanf("%d %d",&pb[i].x,&pb[i].y);
rep(i,1,n)
rep(j,1,k)dis[i][j] = inf;
rep(id,1,k){
int num; std::scanf("%d",&num);
rep(i,1,n)dis[i][id] = inf;
repn(num){
int x; std::scanf("%d",&x);
line[id].push_back(x);
rep(i,1,n)
dis[i][id] = std::min(dis[i][id],sqdis(pa[i],pb[x]));
}
}
int l = 0,r = inf,ans = -1;
while(l <= r){
let mid = (l + r) >> 1;
if(chk(mid))ans = mid,r = mid - 1;
else l = mid + 1;
}
if(ans == -1)return std::puts("-1"),0;
std::printf("%d\n",ans);
getans(ans);
return 0;
}
Compilation message
priglvaci.cpp: In function 'int main()':
priglvaci.cpp:123:15: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
123 | std::scanf("%d %d %d %d",&n,&m,&c,&k);
| ~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
priglvaci.cpp:124:25: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
124 | rep(i,1,n)std::scanf("%d %d",&pa[i].x,&pa[i].y);
| ~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
priglvaci.cpp:125:25: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
125 | rep(i,1,m)std::scanf("%d %d",&pb[i].x,&pb[i].y);
| ~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
priglvaci.cpp:129:28: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
129 | int num; std::scanf("%d",&num);
| ~~~~~~~~~~^~~~~~~~~~~
priglvaci.cpp:132:30: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
132 | int x; std::scanf("%d",&x);
| ~~~~~~~~~~^~~~~~~~~
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
2 ms |
436 KB |
Output is correct |
| 2 |
Correct |
2 ms |
436 KB |
Output is correct |
| 3 |
Correct |
4 ms |
468 KB |
Output is correct |
| 4 |
Correct |
4 ms |
560 KB |
Output is correct |
| 5 |
Correct |
4 ms |
596 KB |
Output is correct |
| 6 |
Correct |
3 ms |
584 KB |
Output is correct |
| 7 |
Correct |
2 ms |
468 KB |
Output is correct |
| 8 |
Correct |
1 ms |
340 KB |
Output is correct |
| 9 |
Correct |
2 ms |
584 KB |
Output is correct |
| 10 |
Correct |
2 ms |
468 KB |
Output is correct |
