Submission #362386

#	Time	Username	Problem	Language	Result	Execution time	Memory
362386		Ahmad_Hasan	Priglavci (COCI18_priglavci)	C++17	96 / 160	5 ms	848 KiB

priglvaci

#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 (stderr)

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++){
      |                     ~^~~~~~~~~~~~~~~~~~

• Subtask 1: 96 / 160