Submission #1053149

#	Time	Username	Problem	Language	Result	Execution time	Memory
1053149		noyancanturk	Fountain Parks (IOI21_parks)	C++17	15 / 100	779 ms	156748 KiB

parks

#include "parks.h"
#include<bits/stdc++.h>
using namespace std;
#define pb push_back
using pii=pair<int,int>;
map<pii,int>fnt;
map<pii,int>roads,bench;
map<int,pii>rev1,rev2;
const int lim=1e6;
vector<int>v[lim];
int ind=1;
int roadcnt;
void connect(pii x,pii y){
    if(!bench.count(y)){
        rev2[ind]=y;
        bench[y]=ind++;
    }
    int i=roads[x],j=bench[y];
    v[i].pb(j);
    v[j].pb(i);
}
const int drain=0;

int match[2*lim],level[lim],p[lim];
int need;

int dfs(int node){
    if(!node)return 1;
    for(int&j=p[node];j<v[node].size();j++){
        if((level[match[node]]==level[node]+1)&&dfs(match[v[node][j]])){
            match[v[node][j]]=node;
            match[node]=v[node][j];
            return 1;
        }
    }
    return 0;
}

int hp(){
    int res=0;
    while(1){
        queue<int>q;
        for(int i=0;i<need;i++){
            level[i]=-1;
            p[i]=0;
            if(i&&!match[i]){
                level[i]=0;
                q.push(i);
            }
        }
        while(q.size()){
            int now=q.front();
            q.pop();
            for(int j:v[now]){
                if(level[match[j]]!=-1)continue;
                level[match[j]]=level[j]+1;
            }
        }
        if(level[drain]==-1)break;
        for(int i=1;i<need;i++){
            if(!match[i]&&dfs(i)){
                res++;
            }
        }
    }
    return res;
}

int parent[lim];
int find(int i){
    if(i==parent[i])return i;
    return parent[i]=find(parent[i]);
}
int unite(int i,int j){
    i=find(i),j=find(j);
    parent[i]=j;
    return i!=j;
}

int construct_roads(std::vector<int> x, std::vector<int> y) {
    int n=x.size();
    for(int i=0;i<n;i++){
        parent[i]=i;
        fnt[{x[i],y[i]}]=i;
    }
    for(int i=0;i<n;i++){
        if(fnt.count({x[i]+2,y[i]})){
            int dude=fnt[{x[i]+2,y[i]}];
            if(!unite(i,dude))continue;
            rev1[ind]={i,dude};
            roads[{x[i]+1,y[i]}]=ind++;
        }
        if(fnt.count({x[i],y[i]+2})){
            int dude=fnt[{x[i],y[i]+2}];
            if(!unite(i,dude))continue;
            rev1[ind]={i,dude};
            roads[{x[i],y[i]+1}]=ind++;
        }
    }
    for(int i=1;i<n;i++){
        if(find(i)!=find(i-1))return 0;
    }
    need=ind;
    for(auto[f,s]:roads){
        if(f.first&1){
            connect(f,pii{f.first,f.second+1});
            connect(f,pii{f.first,f.second-1});
        }else{
            connect(f,pii{f.first+1,f.second});
            connect(f,pii{f.first-1,f.second});
        }
    }
    int k=hp();
    if(k==need-1){
        vector<int>x,y,a,b;
        for(auto[f,s]:rev1){
            x.pb(s.first);
            y.pb(s.second);
            pii ma=rev2[match[f]];
            a.pb(ma.first);
            b.pb(ma.second);
        }
        build(x,y,a,b);
        return 1;
    }
    return 0;
}

Compilation message (stderr)

parks.cpp: In function 'int dfs(int)':
parks.cpp:29:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   29 |     for(int&j=p[node];j<v[node].size();j++){
      |                       ~^~~~~~~~~~~~~~~

• Subtask 1: 5 / 5
• Subtask 2: 10 / 10
• Subtask 3: 0 / 15
• Subtask 4: 0 / 20
• Subtask 5: 0 / 20
• Subtask 6: 0 / 30