#include<bits/stdc++.h>
using namespace std;
const int inf=2e6;
int n, m, c, k;
pair<int, int>u[105], s[105];
vector<int>bus[105], adj[105*2];
int cap[105*2][105*2], par[105*2];
int dst(pair<int, int>A, pair<int, int>B){return (A.first-B.first)*(A.first-B.first)+(A.second-B.second)*(A.second-B.second);}
int bfs(){
memset(par, -1, sizeof(par));
par[0]=-inf;
queue<pair<int, int> >q;
q.push({0, inf}); //source cap inf
for(;!q.empty();q.pop()){
int nw=q.front().first, flw=q.front().second;
for(int nx:adj[nw]) if(par[nx]==-1 && cap[nw][nx]){
par[nx]=nw;
int nflw=min(flw, cap[nw][nx]);
if(nx==201) return nflw; //sink reached
q.push({nx, nflw});
}
}
return 0;
}
int maxflow(){
int mxflw=0, nflw=0;
for(nflw=bfs(); nflw!=0; nflw=bfs()){
mxflw+=nflw;
int nw=201; //retrace path from sink
for(;nw!=0;nw=par[nw]){
cap[par[nw]][nw]-=nflw;
cap[nw][par[nw]]+=nflw; //backedge
}
}
return mxflw;
}
void addedge(int u, int v, int c){
cap[u][v]=c;
adj[u].push_back(v); adj[v].push_back(u);
}
void reset(int lim){
memset(cap, 0, sizeof(cap));
adj[0].clear(); adj[201].clear();
for(int i=1; i<=n; i++)
adj[i].clear(), addedge(0, i, 1);
for(int i=1; i<=k; i++)
adj[100+i].clear(), addedge(100+i, 201, c);
bool kk;
for(int i=1; i<=n; i++){
pair<int, int>nw=u[i];
for(int j=1; j<=k; j++){
kk=false;
for(int nex:bus[j]){
pair<int, int>nx=s[nex];
if(dst(nw, nx)<=lim)
{kk=true; break;}
}
if(kk)
addedge(i, 100+j, 1);
}
}
}
bitset<205>vis;
int main(){
scanf("%d%d%d%d", &n, &m, &c, &k);
for(int i=1; i<=n; i++)
scanf("%d%d", &u[i].first, &u[i].second);
for(int i=1; i<=m; i++)
scanf("%d%d", &s[i].first, &s[i].second);
for(int sz, i=1; i<=k; i++){
scanf("%d", &sz);
for(int j=0, x; j<sz; j++){
scanf("%d", &x);
bus[i].push_back(x);
}
}
int l=0, r=inf, res=inf;
for(int md=(l+r)/2; l<=r; md=(l+r)/2){
reset(md);
int mxflow=maxflow();
if(mxflow==n)
res=md, r=md-1;
else l=md+1;
}
reset(res);
int getmxflw=maxflow();
if(getmxflw!=n){
printf("-1\n");
return 0;
}
printf("%d\n", res);
for(int i=1; i<=n; i++){
pair<int, int>nw=u[i];
for(int j=1; j<=k; j++) if(cap[j+100][i]){
for(int nex:bus[j]){
pair<int, int>nx=s[nex];
if(vis[nex]) continue;
if(dst(nw, nx)<=res){
printf("%d\n", nex);
break;
}
}break;
}
}
return 0;
}
Compilation message
priglvaci.cpp: In function 'int main()':
priglvaci.cpp:65:7: 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:67:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d", &u[i].first, &u[i].second);
~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
priglvaci.cpp:69:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d", &s[i].first, &s[i].second);
~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
priglvaci.cpp:71:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &sz);
~~~~~^~~~~~~~~~~
priglvaci.cpp:73:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &x);
~~~~~^~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
9 ms |
640 KB |
Output is correct |
| 2 |
Correct |
9 ms |
512 KB |
Output is correct |
| 3 |
Correct |
15 ms |
640 KB |
Output is correct |
| 4 |
Correct |
17 ms |
640 KB |
Output is correct |
| 5 |
Correct |
15 ms |
768 KB |
Output is correct |
| 6 |
Correct |
15 ms |
512 KB |
Output is correct |
| 7 |
Correct |
11 ms |
512 KB |
Output is correct |
| 8 |
Correct |
7 ms |
512 KB |
Output is correct |
| 9 |
Correct |
13 ms |
640 KB |
Output is correct |
| 10 |
Correct |
12 ms |
512 KB |
Output is correct |
