Submission #80335

#	Time	Username	Problem	Language	Result	Execution time	Memory
80335		igzi	Priglavci (COCI18_priglavci)	C++17	160 / 160	39 ms	1348 KiB

priglvaci

#include <bits/stdc++.h>
#define maxN 105
#define maxV 505

using namespace std;

bool visited[maxV];
int n,m,c,k,i,j,x,y,ux[maxN],uy[maxN],sx[maxN],sy[maxN];
int rgraph[maxV][maxV];
int ans[maxN];
vector <int> v[maxN];

int dfs(int x,int n,int t,int mf){
visited[x]=true;
if(x==t) return mf;
for(int i=0;i<n;i++){
if(!visited[i] && rgraph[x][i]>0){
    int tmp=dfs(i,n,t,min(mf,rgraph[x][i]));
    if(tmp>0){
        tmp=min(tmp,rgraph[x][i]);
        rgraph[x][i]-=tmp;
        rgraph[i][x]+=tmp;
        return tmp;
    }
}
}
return 0;
}

int maxflow(int n,int s,int t){
memset(visited,false,n+1);
int ans=0,tmp;
tmp=dfs(s,n,t,INT_MAX);
while(tmp){
    ans+=tmp;
    memset(visited,false,n+1);
    tmp=dfs(s,n,t,INT_MAX);
}
return ans;
}

bool blizu(int d,int a,int b){
return (ux[a]-sx[b])*(ux[a]-sx[b])+(uy[a]-sy[b])*(uy[a]-sy[b])<=d;
}

bool resi(int x){
int i,j,t;
for(i=0;i<n+k+2;i++){
    for(j=0;j<n+k+2;j++){
        rgraph[i][j]=0;
    }
}
for(i=1;i<=n;i++) rgraph[0][i]=1;
for(i=1;i<=n;i++){
    for(j=n+1;j<=n+k;j++){
        rgraph[i][j]=0;
        for(t=0;t<v[j-n-1].size();t++){
            if(blizu(x,i-1,v[j-n-1][t])) {rgraph[i][j]=1; break;}
        }
    }
}
for(i=n+1;i<=n+k;i++) rgraph[i][n+k+1]=c;
return n<=maxflow(n+k+2,0,n+k+1);
}

int nadji(int x,int a,int b){
for(int i=0;i<v[b].size();i++){
    if(blizu(x,a,v[b][i])) return v[b][i]+1;
}
}

void resi2(int x){
int i,j,t,graph[maxV][maxV];
for(i=0;i<n+k+2;i++){
    for(j=0;j<n+k+2;j++){
        graph[i][j]=rgraph[i][j]=0;
    }
}
for(i=1;i<=n;i++) {graph[0][i]=1; rgraph[0][i]=1;}
for(i=1;i<=n;i++){
    for(j=n+1;j<=n+k;j++){
        graph[i][j]=0;
        for(t=0;t<v[j-n-1].size();t++){
            if(blizu(x,i-1,v[j-n-1][t])) {graph[i][j]=1; break;}
        }
        rgraph[i][j]=graph[i][j];
    }
}
for(i=n+1;i<=n+k;i++) {graph[i][n+k+1]=c; rgraph[i][n+k+1]=c;}
maxflow(n+k+2,0,n+k+1);
for(i=1;i<=n;i++){
    for(j=n+1;j<=n+k;j++){
        if(rgraph[i][j]<graph[i][j]){
            ans[i-1]=nadji(x,i-1,j-n-1);
            break;
        }
    }
}
}

int main()
{
    std::ios_base::sync_with_stdio(false);
    cin>>n>>m>>c>>k;
    for(i=0;i<n;i++) cin>>ux[i]>>uy[i];
    for(i=0;i<m;i++) cin>>sx[i]>>sy[i];
    for(i=0;i<k;i++){
        cin>>x;
        for(j=0;j<x;j++){
            cin>>y;
            v[i].push_back(y-1);
        }
    }
    int l,d,m;
    l=0;
    d=10000000;
    while(d>l){
        m=(l+d)/2;
        if(resi(m)) d=m;
        else l=m+1;
    }
    if(l==10000000) {cout<<-1<<endl; return 0;}
    cout<<l<<endl;
    resi2(l);
    for(i=0;i<n;i++){
        cout<<ans[i]<<"\n";
    }
    return 0;
}

Compilation message (stderr)

priglvaci.cpp: In function 'bool resi(int)':
priglvaci.cpp:57:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(t=0;t<v[j-n-1].size();t++){
                 ~^~~~~~~~~~~~~~~~
priglvaci.cpp: In function 'int nadji(int, int, int)':
priglvaci.cpp:67:14: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 for(int i=0;i<v[b].size();i++){
             ~^~~~~~~~~~~~
priglvaci.cpp: In function 'void resi2(int)':
priglvaci.cpp:83:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(t=0;t<v[j-n-1].size();t++){
                 ~^~~~~~~~~~~~~~~~
priglvaci.cpp: In function 'int nadji(int, int, int)':
priglvaci.cpp:70:1: warning: control reaches end of non-void function [-Wreturn-type]
 }
 ^

• Subtask 1: 160 / 160