#include <bits/stdc++.h>
#define int long long
/**
|||||||||| ||||| ||||| ||||||||||
||||||||||||| ||||| ||||| |||||
|||| |||||| ||||| ||||| |||||
||||||||||||||||| ||||||||||||||| ||||||||||
||||||||||||||||||| ||||||||||||||| |||||
||||| ||||| ||||| ||||| |||||
||||| ||||| ||||| ||||| ||||||||||
AHMED;HASSAN;SAEED;
*/
using namespace std;
int n,m,c,k;
vector<int>cap(m);
vector<int>rmn;
vector<vector<int> >adj[2];
vector<vector<int> >cst;
vector<int>vis[2];
vector<vector<int> >mtch;
vector<int>lins;
vector<vector<int> >cncts;
int mx;
int cstdis(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);
}
bool can(int cr,int f,int p=-1){
///cout<<cr<<' '<<f<<'\n';
if(vis[f][cr])
return false;
vis[f][cr]=1;
if(!f){
bool ret=false;
for(int i=0;i<adj[f][cr].size();i++){
int to=adj[f][cr][i];
if(cst[cr][to]<=mx){
if(can(to,!f,cr)){
return true;
}
}
}
return ret;
}else{
///cout<<'#'<<rmn[cr]<<'\n';
for(int i=0;i<cncts[cr].size();i++){
if(lins[cncts[cr][i]]){
mtch[p][cr]=1;
lins[cncts[cr][i]]--;
return true;
}
}
bool ret=false;
for(int i=0;i<adj[f][cr].size();i++){
int to=adj[f][cr][i];
if(mtch[to][cr]&&can(to,!f,cr)){
mtch[p][cr]=1;
mtch[to][cr]=0;
return true;
}
}
return ret;
}
}
bool match(){
vis[0]=vector<int>(n,0);
vis[1]=vector<int>(m,0);
lins=vector<int>(k,c);
rmn=cap;
mtch=vector<vector<int> >(n,vector<int>(m));
for(int i=0;i<n;i++){
vis[1]=vector<int>(m,0);
///cout<<i<<'\n';
if(!can(i,0))
return false;
}
///cout<<'h'<<'\n';
return true;
}
int32_t main()
{
ios_base::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
cin>>n>>m>>c>>k;
vector<pair<int,int> >stds(n),stns(m);
cap=vector<int>(m);
for(int i=0;i<n;i++){
int x,y;
cin>>x>>y;
stds[i]={x,y};
}
for(int i=0;i<m;i++){
int x,y;
cin>>x>>y;
stns[i]={x,y};
}
cncts.resize(m);
for(int i=0;i<k;i++){
int kn;
cin>>kn;
for(int j=0;j<kn;j++){
int tm;
cin>>tm;
cap[tm-1]+=c;
cncts[tm-1].push_back(i);
}
}
if(k*c<n){
cout<<-1<<'\n';
return 0;
}
adj[0].resize(n);
adj[1].resize(m);
cst=vector<vector<int> >(n,vector<int>(m,0));
int l=0,r=-1;
for(int i=0;i<n;i++){
for(int j=0;j<m;j++){
int dis=cstdis(stds[i],stns[j]);
adj[0][i].push_back(j);
adj[1][j].push_back(i);
cst[i][j]=dis;
r=max(r,dis);
}
}
int ans=0;
while(l<=r){
mx=(r-l)/2+l;
if(match()){
ans=mx;
r=mx-1;
}else{
l=mx+1;
}
}
cout<<ans<<'\n';
mx=ans;
match();
for(int i=0;i<n;i++){
for(int j=0;j<m;j++){
if(mtch[i][j]){
cout<<j+1<<'\n';
break;
}
}
}
return 0;
}
Compilation message
priglvaci.cpp: In function 'bool can(long long int, long long int, long long int)':
priglvaci.cpp:37:22: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
37 | for(int i=0;i<adj[f][cr].size();i++){
| ~^~~~~~~~~~~~~~~~~~
priglvaci.cpp:49:22: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
49 | for(int i=0;i<cncts[cr].size();i++){
| ~^~~~~~~~~~~~~~~~~
priglvaci.cpp:58:22: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
58 | for(int i=0;i<adj[f][cr].size();i++){
| ~^~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
620 KB |
Output isn't correct |
| 2 |
Incorrect |
2 ms |
492 KB |
Output isn't correct |
| 3 |
Correct |
0 ms |
364 KB |
Output is correct |
| 4 |
Correct |
5 ms |
748 KB |
Output is correct |
| 5 |
Incorrect |
5 ms |
748 KB |
Output isn't correct |
| 6 |
Correct |
2 ms |
620 KB |
Output is correct |
| 7 |
Incorrect |
3 ms |
492 KB |
Output isn't correct |
| 8 |
Correct |
2 ms |
492 KB |
Output is correct |
| 9 |
Correct |
1 ms |
620 KB |
Output is correct |
| 10 |
Correct |
2 ms |
848 KB |
Output is correct |
