Submission #974526

#	Time	Username	Problem	Language	Result	Execution time	Memory
974526		onlk97	Fountain Parks (IOI21_parks)	C++17	5 / 100	372 ms	58420 KiB

parks

#include "parks.h"
#include <bits/stdc++.h>
using namespace std;
int dsu[200010],L,R;
vector <int> g[200010],match1,match2,dist;
int prt(int n){
    if (dsu[n]==n) return n;
    return dsu[n]=prt(dsu[n]);
}
void unn(int u,int v){
    dsu[prt(u)]=dsu[prt(v)];
}
map <pair <int,int>,int> mp;
vector <pair <int,int> > vmp;
int gt(int u,int v){
    if (mp.find({u,v})==mp.end()){
        mp[{u,v}]=mp.size()+1;
        vmp.push_back({u,v});
    }
    return mp[{u,v}];
}
void bfs(){
    dist.clear();
    for (int i=0; i<L; i++) dist.push_back(-1);
    queue <int> q;
    for (int i=0; i<L; i++){
        if (match1[i]==-1){
            dist[i]=0;
            q.push(i);
        }
    }
    while (!q.empty()){
        int tp=q.front(); q.pop();
        for (int i:g[tp]){
            if (match2[i]!=-1&&dist[match2[i]]==-1){
                dist[match2[i]]=dist[tp]+1;
                q.push(match2[i]);
            }
        }
    }
}
int dfs(int cur){
    for (int i:g[cur]){
        if (match2[i]==-1){
            match1[cur]=i;
            match2[i]=cur;
            return 1;
        }
    }
    for (int i:g[cur]){
        if (dist[match2[i]]==dist[cur]+1&&dfs(match2[i])){
            match1[cur]=i;
            match2[i]=cur;
            return 1;
        }
    }
    return 0;
}
bool cmp(pair <pair <int,int>,int> u,pair <pair <int,int>,int> v){
    if (u.first.second!=v.first.second) return u.first.second<v.first.second;
    return u.first.first<v.first.first;
}
int construct_roads(vector <int> x,vector <int> y){
    int n=x.size();
    pair <pair <int,int>,int> a[n];
    for (int i=0; i<n; i++) a[i]={{x[i],y[i]},i};
    pair <int,int> cpy[n];
    for (int i=0; i<n; i++) cpy[i]={x[i],y[i]};
    sort(a,a+n);
    for (int i=0; i<n; i++) dsu[i]=i;
    vector <int> u,v,A,B;
    vmp.push_back({-1,-1});
    vector <pair <int,int> > hor,ver;
    for (int i=1; i<n; i++){
        if (a[i-1].first.first==a[i].first.first&&a[i-1].first.second+2==a[i].first.second){
            ver.push_back({a[i-1].second,a[i].second});
        }
    }
    sort(a,a+n,cmp);
    for (int i=1; i<n; i++){
        if (a[i-1].first.first+2==a[i].first.first&&a[i-1].first.second==a[i].first.second){
            hor.push_back({a[i-1].second,a[i].second});
        }
    }
    int cnt=0;
    for (int iters=0; iters<n; iters++){
        if (hor.size()>iters&&prt(hor[iters].first)!=prt(hor[iters].second)){
            u.push_back(hor[iters].first);
            v.push_back(hor[iters].second);
            unn(hor[iters].first,hor[iters].second);
            int tp=gt(cpy[hor[iters].first].first-1,cpy[hor[iters].first].second+1);
            g[cnt].push_back(tp);
            tp=gt(cpy[hor[iters].first].first+1,cpy[hor[iters].first].second+1);
            g[cnt].push_back(tp);
            cnt++;
        }
        if (ver.size()>iters&&prt(ver[iters].first)!=prt(ver[iters].second)){
            u.push_back(ver[iters].first);
            v.push_back(ver[iters].second);
            unn(ver[iters].first,ver[iters].second);
            int tp=gt(cpy[ver[iters].first].first-1,cpy[ver[iters].first].second+1);
            g[cnt].push_back(tp);
            tp=gt(cpy[ver[iters].first].first+1,cpy[ver[iters].first].second+1);
            g[cnt].push_back(tp);
            cnt++;
        }
        if (hor.size()>iters+1&&prt(hor.back().first)!=prt(hor.back().second)){
            u.push_back(hor.back().first);
            v.push_back(hor.back().second);
            unn(hor.back().first,hor.back().second);
            int tp=gt(cpy[hor.back().first].first-1,cpy[hor.back().first].second+1);
            g[cnt].push_back(tp);
            tp=gt(cpy[hor.back().first].first+1,cpy[hor.back().first].second+1);
            g[cnt].push_back(tp);
            cnt++;
            hor.pop_back();
        }
        if (ver.size()>iters+1&&prt(ver.back().first)!=prt(ver.back().second)){
            u.push_back(ver.back().first);
            v.push_back(ver.back().second);
            unn(ver.back().first,ver.back().second);
            int tp=gt(cpy[ver.back().first].first-1,cpy[ver.back().first].second+1);
            g[cnt].push_back(tp);
            tp=gt(cpy[ver.back().first].first+1,cpy[ver.back().first].second+1);
            g[cnt].push_back(tp);
            cnt++;
            ver.pop_back();
        }
    }
    for (int i=1; i<n; i++){
        if (prt(a[i].second)!=prt(a[0].second)) return 0;
    }
    for (int i=0; i<n-1; i++) match1.push_back(-1);
    for (int i=0; i<=vmp.size(); i++) match2.push_back(-1);
    L=match1.size(); R=match2.size();
    int flo=0;
    while (1){
        bfs();
        int aug=0;
        for (int i=0; i<L; i++){
            if (match1[i]==-1) aug+=dfs(i);
        }
        if (!aug) break;
        flo+=aug;
    }
    if (flo!=L) return 0;
    for (int i=0; i<L; i++){
        int tp=match1[i];
        A.push_back(vmp[tp].first);
        B.push_back(vmp[tp].second);
    }
    build(u,v,A,B);
    return 1;
}

Compilation message (stderr)

parks.cpp: In function 'int construct_roads(std::vector<int>, std::vector<int>)':
parks.cpp:87:23: warning: comparison of integer expressions of different signedness: 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   87 |         if (hor.size()>iters&&prt(hor[iters].first)!=prt(hor[iters].second)){
      |             ~~~~~~~~~~^~~~~~
parks.cpp:97:23: warning: comparison of integer expressions of different signedness: 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   97 |         if (ver.size()>iters&&prt(ver[iters].first)!=prt(ver[iters].second)){
      |             ~~~~~~~~~~^~~~~~
parks.cpp:107:23: warning: comparison of integer expressions of different signedness: 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  107 |         if (hor.size()>iters+1&&prt(hor.back().first)!=prt(hor.back().second)){
      |             ~~~~~~~~~~^~~~~~~~
parks.cpp:118:23: warning: comparison of integer expressions of different signedness: 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  118 |         if (ver.size()>iters+1&&prt(ver.back().first)!=prt(ver.back().second)){
      |             ~~~~~~~~~~^~~~~~~~
parks.cpp:134:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  134 |     for (int i=0; i<=vmp.size(); i++) match2.push_back(-1);
      |                   ~^~~~~~~~~~~~

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