oj.uz

Submission #609810

# Submission time Handle Problem Language Result Execution time Memory
609810 2022-07-27T23:10:49 Z StrawHatWess Fountain Parks (IOI21_parks) C++17
5 / 100
 153 ms 43516 KB 
#include "parks.h"

#include <bits/stdc++.h>
using namespace std; 

#define FOR(i,a,b) for(int i=a; i<b; i++)
typedef long long ll;
typedef vector<int>vi;
#define pb push_back
#define sz(x) (int)x.size()
#define all(x) begin(x),end(x)


typedef pair<int,int>pi; 
#define fi first
#define se second
typedef vector<pi>vpi;
#define eb emplace_back

bool ckmin(int &x, int y){
    bool f=(x>y); 
    x=min(x,y); 
    return f; 
}

bool ckmax(int &x, int y){
    bool f=(x<y); 
    x=max(x,y); 
    return f; 
}

//-------


const int MX=2e5+100;


vi rnk(MX,0), p(MX); 
int findSet(int i){return p[i]==i ? i : p[i]=findSet(p[i]); }

void unionSet(int u, int v){
    u=findSet(u), v=findSet(v); 

    if(rnk[u]<rnk[v]) swap(u,v); 
    if(rnk[u]==rnk[v]) rnk[u]++; 

    p[v]=u; 
}



int N; 
vi X, Y; 

bool cmp(pi a, pi b){
    int i=a.fi, j=a.se, k=b.fi, l=b.se; 
    if(X[i]!=X[k]) return X[i] < X[k]; 
    return X[i]==X[j];
}


unordered_map<int,int>pos[MX], vis[MX]; 
int construct_roads(vi X, vi Y) {
    N=sz(X); 
    ::X=X; ::Y=Y; 

    if (N==1) {
        build({}, {}, {}, {});
        return 1;
    }
    
   
    FOR(i,0,N) pos[X[i]][Y[i]]=i, p[i]=i; 


    //building vertical 
    vpi roads; 
    FOR(i,0,N){
        int x=X[i], y=Y[i]; 
        if(pos[x].count(y-2)){
            int j=pos[x][y-2]; 
            if(findSet(i)!=findSet(j)){
                roads.eb(j,i);
                unionSet(i,j); 
            }
            
        }
    }
    //building horizontal
    /*FOR(i,0,N){
        int x=X[i], y=Y[i]; 
        if(pos[x-2].count(y)){
            int j=pos[x-2][y]; 
            if(findSet(i)!=findSet(j)){
                roads.eb(j,i);
                unionSet(i,j); 
            }
        }
    }*/


    //checking connectivity
    FOR(i,0,N) if(findSet(i)!=findSet(0)) return 0; 

    //sort(all(roads),cmp); //debug its correctness

    vi u,v,A,B; 
    for(auto it: roads){
        int i=it.fi, j=it.se; 
        u.pb(i); v.pb(j); 

        if(X[i]==X[j]){
            //vertical
            int x=X[i], y=Y[i]; 

            if(!vis[x-1].count(y+1)){
                A.pb(x-1); B.pb(y+1); 
                vis[x-1][y+1]=1; 
            }
            else{
                if(vis[x+1].count(y+1)) return 0; 

                A.pb(x+1); B.pb(y+1); 
                vis[x+1][y+1]=1; 
            }
        }
        else{
            //horizontal
            int x=X[i], y=Y[i];  

            if(!vis[x+1].count(y+1)){
                A.pb(x+1); B.pb(y+1); 
                vis[x+1][y+1]=1; 
            }
            else{
                if(vis[x+1].count(y-1)) return 0; 

                A.pb(x+1); B.pb(y-1); 
                vis[x+1][y-1]=1; 
            }

        }
    }



    build(u, v, A, B);
    return 1;
}


/*
5
4 4
4 6
6 4
4 2
2 4

1
4
0 2 5 5
0 1 3 5
3 0 5 3
4 0 3 3




*/

/*

2
2 2
4 6

0


*/

Compilation message

parks.cpp: In function 'bool cmp(pi, pi)':
parks.cpp:56:33: warning: unused variable 'l' [-Wunused-variable]
   56 |     int i=a.fi, j=a.se, k=b.fi, l=b.se;
      |                                 ^

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 23764 KB Output is correct
2 Correct 16 ms 23764 KB Output is correct
3 Correct 12 ms 23764 KB Output is correct
4 Correct 12 ms 23764 KB Output is correct
5 Correct 12 ms 23688 KB Output is correct
6 Correct 12 ms 23712 KB Output is correct
7 Correct 12 ms 23764 KB Output is correct
8 Correct 12 ms 23764 KB Output is correct
9 Correct 92 ms 41324 KB Output is correct
10 Correct 19 ms 25604 KB Output is correct
11 Correct 46 ms 33456 KB Output is correct
12 Correct 22 ms 26560 KB Output is correct
13 Correct 26 ms 28060 KB Output is correct
14 Correct 13 ms 23764 KB Output is correct
15 Correct 14 ms 23936 KB Output is correct
16 Correct 92 ms 41916 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 23764 KB Output is correct
2 Correct 16 ms 23764 KB Output is correct
3 Correct 12 ms 23764 KB Output is correct
4 Correct 12 ms 23764 KB Output is correct
5 Correct 12 ms 23688 KB Output is correct
6 Correct 12 ms 23712 KB Output is correct
7 Correct 12 ms 23764 KB Output is correct
8 Correct 12 ms 23764 KB Output is correct
9 Correct 92 ms 41324 KB Output is correct
10 Correct 19 ms 25604 KB Output is correct
11 Correct 46 ms 33456 KB Output is correct
12 Correct 22 ms 26560 KB Output is correct
13 Correct 26 ms 28060 KB Output is correct
14 Correct 13 ms 23764 KB Output is correct
15 Correct 14 ms 23936 KB Output is correct
16 Correct 92 ms 41916 KB Output is correct
17 Incorrect 13 ms 23736 KB Solution announced impossible, but it is possible.
18 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 23764 KB Output is correct
2 Correct 16 ms 23764 KB Output is correct
3 Correct 12 ms 23764 KB Output is correct
4 Correct 12 ms 23764 KB Output is correct
5 Correct 12 ms 23688 KB Output is correct
6 Correct 12 ms 23712 KB Output is correct
7 Correct 12 ms 23764 KB Output is correct
8 Correct 12 ms 23764 KB Output is correct
9 Correct 92 ms 41324 KB Output is correct
10 Correct 19 ms 25604 KB Output is correct
11 Correct 46 ms 33456 KB Output is correct
12 Correct 22 ms 26560 KB Output is correct
13 Correct 26 ms 28060 KB Output is correct
14 Correct 13 ms 23764 KB Output is correct
15 Correct 14 ms 23936 KB Output is correct
16 Correct 92 ms 41916 KB Output is correct
17 Incorrect 13 ms 23736 KB Solution announced impossible, but it is possible.
18 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 23764 KB Output is correct
2 Correct 16 ms 23764 KB Output is correct
3 Correct 12 ms 23764 KB Output is correct
4 Correct 12 ms 23764 KB Output is correct
5 Correct 12 ms 23688 KB Output is correct
6 Correct 12 ms 23712 KB Output is correct
7 Correct 12 ms 23764 KB Output is correct
8 Correct 12 ms 23764 KB Output is correct
9 Correct 92 ms 41324 KB Output is correct
10 Correct 19 ms 25604 KB Output is correct
11 Correct 46 ms 33456 KB Output is correct
12 Correct 22 ms 26560 KB Output is correct
13 Correct 26 ms 28060 KB Output is correct
14 Correct 13 ms 23764 KB Output is correct
15 Correct 14 ms 23936 KB Output is correct
16 Correct 92 ms 41916 KB Output is correct
17 Incorrect 12 ms 23764 KB Solution announced impossible, but it is possible.
18 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 23764 KB Output is correct
2 Correct 16 ms 23764 KB Output is correct
3 Correct 12 ms 23764 KB Output is correct
4 Correct 12 ms 23764 KB Output is correct
5 Correct 12 ms 23688 KB Output is correct
6 Correct 12 ms 23712 KB Output is correct
7 Correct 12 ms 23764 KB Output is correct
8 Correct 12 ms 23764 KB Output is correct
9 Correct 92 ms 41324 KB Output is correct
10 Correct 19 ms 25604 KB Output is correct
11 Correct 46 ms 33456 KB Output is correct
12 Correct 22 ms 26560 KB Output is correct
13 Correct 26 ms 28060 KB Output is correct
14 Correct 13 ms 23764 KB Output is correct
15 Correct 14 ms 23936 KB Output is correct
16 Correct 92 ms 41916 KB Output is correct
17 Incorrect 153 ms 43516 KB Solution announced impossible, but it is possible.
18 Halted 0 ms 0 KB -

Subtask #6
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 23764 KB Output is correct
2 Correct 16 ms 23764 KB Output is correct
3 Correct 12 ms 23764 KB Output is correct
4 Correct 12 ms 23764 KB Output is correct
5 Correct 12 ms 23688 KB Output is correct
6 Correct 12 ms 23712 KB Output is correct
7 Correct 12 ms 23764 KB Output is correct
8 Correct 12 ms 23764 KB Output is correct
9 Correct 92 ms 41324 KB Output is correct
10 Correct 19 ms 25604 KB Output is correct
11 Correct 46 ms 33456 KB Output is correct
12 Correct 22 ms 26560 KB Output is correct
13 Correct 26 ms 28060 KB Output is correct
14 Correct 13 ms 23764 KB Output is correct
15 Correct 14 ms 23936 KB Output is correct
16 Correct 92 ms 41916 KB Output is correct
17 Incorrect 13 ms 23736 KB Solution announced impossible, but it is possible.
18 Halted 0 ms 0 KB -