oj.uz

Submission #974526

# Submission time Handle Problem Language Result Execution time Memory
974526 2024-05-03T12:19:35 Z onlk97 Fountain Parks (IOI21_parks) C++17
5 / 100
 372 ms 58420 KB 
#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

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

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4956 KB Output is correct
2 Correct 1 ms 4956 KB Output is correct
3 Correct 1 ms 4956 KB Output is correct
4 Correct 1 ms 4956 KB Output is correct
5 Correct 1 ms 4956 KB Output is correct
6 Correct 1 ms 4956 KB Output is correct
7 Correct 2 ms 4956 KB Output is correct
8 Correct 2 ms 4952 KB Output is correct
9 Correct 164 ms 34956 KB Output is correct
10 Correct 13 ms 8140 KB Output is correct
11 Correct 77 ms 21076 KB Output is correct
12 Correct 19 ms 9564 KB Output is correct
13 Correct 48 ms 15348 KB Output is correct
14 Correct 3 ms 5208 KB Output is correct
15 Correct 3 ms 5464 KB Output is correct
16 Correct 160 ms 34768 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4956 KB Output is correct
2 Correct 1 ms 4956 KB Output is correct
3 Correct 1 ms 4956 KB Output is correct
4 Correct 1 ms 4956 KB Output is correct
5 Correct 1 ms 4956 KB Output is correct
6 Correct 1 ms 4956 KB Output is correct
7 Correct 2 ms 4956 KB Output is correct
8 Correct 2 ms 4952 KB Output is correct
9 Correct 164 ms 34956 KB Output is correct
10 Correct 13 ms 8140 KB Output is correct
11 Correct 77 ms 21076 KB Output is correct
12 Correct 19 ms 9564 KB Output is correct
13 Correct 48 ms 15348 KB Output is correct
14 Correct 3 ms 5208 KB Output is correct
15 Correct 3 ms 5464 KB Output is correct
16 Correct 160 ms 34768 KB Output is correct
17 Incorrect 1 ms 4952 KB Tree (a[0], b[0]) = (1, 3) is not adjacent to edge between u[0]=3 @(2, 2) and v[0]=2 @(4, 2)
18 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4956 KB Output is correct
2 Correct 1 ms 4956 KB Output is correct
3 Correct 1 ms 4956 KB Output is correct
4 Correct 1 ms 4956 KB Output is correct
5 Correct 1 ms 4956 KB Output is correct
6 Correct 1 ms 4956 KB Output is correct
7 Correct 2 ms 4956 KB Output is correct
8 Correct 2 ms 4952 KB Output is correct
9 Correct 164 ms 34956 KB Output is correct
10 Correct 13 ms 8140 KB Output is correct
11 Correct 77 ms 21076 KB Output is correct
12 Correct 19 ms 9564 KB Output is correct
13 Correct 48 ms 15348 KB Output is correct
14 Correct 3 ms 5208 KB Output is correct
15 Correct 3 ms 5464 KB Output is correct
16 Correct 160 ms 34768 KB Output is correct
17 Incorrect 1 ms 4952 KB Tree (a[0], b[0]) = (1, 3) is not adjacent to edge between u[0]=3 @(2, 2) and v[0]=2 @(4, 2)
18 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4956 KB Output is correct
2 Correct 1 ms 4956 KB Output is correct
3 Correct 1 ms 4956 KB Output is correct
4 Correct 1 ms 4956 KB Output is correct
5 Correct 1 ms 4956 KB Output is correct
6 Correct 1 ms 4956 KB Output is correct
7 Correct 2 ms 4956 KB Output is correct
8 Correct 2 ms 4952 KB Output is correct
9 Correct 164 ms 34956 KB Output is correct
10 Correct 13 ms 8140 KB Output is correct
11 Correct 77 ms 21076 KB Output is correct
12 Correct 19 ms 9564 KB Output is correct
13 Correct 48 ms 15348 KB Output is correct
14 Correct 3 ms 5208 KB Output is correct
15 Correct 3 ms 5464 KB Output is correct
16 Correct 160 ms 34768 KB Output is correct
17 Incorrect 2 ms 4956 KB Tree (a[0], b[0]) = (199997, 3) is not adjacent to edge between u[0]=2 @(199998, 2) and v[0]=0 @(200000, 2)
18 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4956 KB Output is correct
2 Correct 1 ms 4956 KB Output is correct
3 Correct 1 ms 4956 KB Output is correct
4 Correct 1 ms 4956 KB Output is correct
5 Correct 1 ms 4956 KB Output is correct
6 Correct 1 ms 4956 KB Output is correct
7 Correct 2 ms 4956 KB Output is correct
8 Correct 2 ms 4952 KB Output is correct
9 Correct 164 ms 34956 KB Output is correct
10 Correct 13 ms 8140 KB Output is correct
11 Correct 77 ms 21076 KB Output is correct
12 Correct 19 ms 9564 KB Output is correct
13 Correct 48 ms 15348 KB Output is correct
14 Correct 3 ms 5208 KB Output is correct
15 Correct 3 ms 5464 KB Output is correct
16 Correct 160 ms 34768 KB Output is correct
17 Incorrect 372 ms 58420 KB Tree (a[0], b[0]) = (1, 3) is not adjacent to edge between u[0]=199575 @(2, 2) and v[0]=22196 @(4, 2)
18 Halted 0 ms 0 KB -

Subtask #6
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4956 KB Output is correct
2 Correct 1 ms 4956 KB Output is correct
3 Correct 1 ms 4956 KB Output is correct
4 Correct 1 ms 4956 KB Output is correct
5 Correct 1 ms 4956 KB Output is correct
6 Correct 1 ms 4956 KB Output is correct
7 Correct 2 ms 4956 KB Output is correct
8 Correct 2 ms 4952 KB Output is correct
9 Correct 164 ms 34956 KB Output is correct
10 Correct 13 ms 8140 KB Output is correct
11 Correct 77 ms 21076 KB Output is correct
12 Correct 19 ms 9564 KB Output is correct
13 Correct 48 ms 15348 KB Output is correct
14 Correct 3 ms 5208 KB Output is correct
15 Correct 3 ms 5464 KB Output is correct
16 Correct 160 ms 34768 KB Output is correct
17 Incorrect 1 ms 4952 KB Tree (a[0], b[0]) = (1, 3) is not adjacent to edge between u[0]=3 @(2, 2) and v[0]=2 @(4, 2)
18 Halted 0 ms 0 KB -