oj.uz

Submission #1053129

# Submission time Handle Problem Language Result Execution time Memory
1053129 2024-08-11T08:57:22 Z noyancanturk Fountain Parks (IOI21_parks) C++17
0 / 100
 4 ms 27060 KB 
#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 construct_roads(std::vector<int> x, std::vector<int> y) {
    int n=x.size();
    for(int i=0;i<n;i++){
        fnt[{x[i],y[i]}]=i;
    }
    for(int i=0;i<n;i++){
        if(fnt.count({x[i]+2,y[i]})){
            rev1[ind]={i,fnt[{x[i]+2,y[i]}]};
            roads[{x[i]+1,y[i]}]=ind++;
        }
        if(fnt.count({x[i],y[i]+2})){
            rev1[ind]={i,fnt[{x[i],y[i]+2}]};
            roads[{x[i],y[i]+1}]=ind++;
        }
    }
    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

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
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 26968 KB Output is correct
2 Correct 4 ms 26972 KB Output is correct
3 Incorrect 4 ms 27060 KB Given structure is not connected: There is no path between vertices 0 and 1
4 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 26968 KB Output is correct
2 Correct 4 ms 26972 KB Output is correct
3 Incorrect 4 ms 27060 KB Given structure is not connected: There is no path between vertices 0 and 1
4 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 26968 KB Output is correct
2 Correct 4 ms 26972 KB Output is correct
3 Incorrect 4 ms 27060 KB Given structure is not connected: There is no path between vertices 0 and 1
4 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 26968 KB Output is correct
2 Correct 4 ms 26972 KB Output is correct
3 Incorrect 4 ms 27060 KB Given structure is not connected: There is no path between vertices 0 and 1
4 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 26968 KB Output is correct
2 Correct 4 ms 26972 KB Output is correct
3 Incorrect 4 ms 27060 KB Given structure is not connected: There is no path between vertices 0 and 1
4 Halted 0 ms 0 KB -

Subtask #6
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 26968 KB Output is correct
2 Correct 4 ms 26972 KB Output is correct
3 Incorrect 4 ms 27060 KB Given structure is not connected: There is no path between vertices 0 and 1
4 Halted 0 ms 0 KB -