Submission #974510

#	Time	Username	Problem	Language	Result	Execution time	Memory
974510		onlk97	Fountain Parks (IOI21_parks)	C++17	70 / 100	360 ms	65844 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};
    sort(a,a+n);
    for (int i=0; i<n; i++) dsu[i]=i;
    vector <int> u,v,A,B;
    int cnt=0;
    vmp.push_back({-1,-1});
    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&&prt(a[i-1].second)!=prt(a[i].second)){
            u.push_back(a[i-1].second);
            v.push_back(a[i].second);
            unn(a[i-1].second,a[i].second);
            int tp=gt(a[i].first.first-1,a[i].first.second-1);
            g[cnt].push_back(tp);
            tp=gt(a[i].first.first+1,a[i].first.second-1);
            g[cnt].push_back(tp);
            cnt++;
        }
    }
    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&&prt(a[i-1].second)!=prt(a[i].second)){
            u.push_back(a[i-1].second);
            v.push_back(a[i].second);
            unn(a[i-1].second,a[i].second);
            int tp=gt(a[i].first.first-1,a[i].first.second-1);
            g[cnt].push_back(tp);
            tp=gt(a[i].first.first-1,a[i].first.second+1);
            g[cnt].push_back(tp);
            cnt++;
        }
    }
    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();
    while (1){
        bfs();
        int aug=0;
        for (int i=0; i<L; i++){
            if (match1[i]==-1) aug+=dfs(i);
        }
        if (!aug) break;
    }
    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:101: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]
  101 |     for (int i=0; i<=vmp.size(); i++) match2.push_back(-1);
      |                   ~^~~~~~~~~~~~

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