oj.uz

Submission #609811

# Submission time Handle Problem Language Result Execution time Memory
609811 2022-07-27T23:11:36 Z StrawHatWess Fountain Parks (IOI21_parks) C++17
5 / 100
 332 ms 76724 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 13 ms 23764 KB Output is correct
2 Correct 13 ms 23696 KB Output is correct
3 Correct 15 ms 23796 KB Output is correct
4 Correct 12 ms 23764 KB Output is correct
5 Correct 13 ms 23764 KB Output is correct
6 Correct 12 ms 23772 KB Output is correct
7 Correct 12 ms 23764 KB Output is correct
8 Correct 13 ms 23764 KB Output is correct
9 Correct 96 ms 41296 KB Output is correct
10 Correct 19 ms 25472 KB Output is correct
11 Correct 50 ms 32964 KB Output is correct
12 Correct 23 ms 26452 KB Output is correct
13 Correct 24 ms 27748 KB Output is correct
14 Correct 13 ms 23820 KB Output is correct
15 Correct 14 ms 23920 KB Output is correct
16 Correct 95 ms 41300 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 23764 KB Output is correct
2 Correct 13 ms 23696 KB Output is correct
3 Correct 15 ms 23796 KB Output is correct
4 Correct 12 ms 23764 KB Output is correct
5 Correct 13 ms 23764 KB Output is correct
6 Correct 12 ms 23772 KB Output is correct
7 Correct 12 ms 23764 KB Output is correct
8 Correct 13 ms 23764 KB Output is correct
9 Correct 96 ms 41296 KB Output is correct
10 Correct 19 ms 25472 KB Output is correct
11 Correct 50 ms 32964 KB Output is correct
12 Correct 23 ms 26452 KB Output is correct
13 Correct 24 ms 27748 KB Output is correct
14 Correct 13 ms 23820 KB Output is correct
15 Correct 14 ms 23920 KB Output is correct
16 Correct 95 ms 41300 KB Output is correct
17 Correct 13 ms 23764 KB Output is correct
18 Correct 13 ms 23736 KB Output is correct
19 Correct 12 ms 23812 KB Output is correct
20 Correct 13 ms 23816 KB Output is correct
21 Correct 13 ms 23764 KB Output is correct
22 Correct 13 ms 23760 KB Output is correct
23 Incorrect 183 ms 52468 KB Solution announced impossible, but it is possible.
24 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 23764 KB Output is correct
2 Correct 13 ms 23696 KB Output is correct
3 Correct 15 ms 23796 KB Output is correct
4 Correct 12 ms 23764 KB Output is correct
5 Correct 13 ms 23764 KB Output is correct
6 Correct 12 ms 23772 KB Output is correct
7 Correct 12 ms 23764 KB Output is correct
8 Correct 13 ms 23764 KB Output is correct
9 Correct 96 ms 41296 KB Output is correct
10 Correct 19 ms 25472 KB Output is correct
11 Correct 50 ms 32964 KB Output is correct
12 Correct 23 ms 26452 KB Output is correct
13 Correct 24 ms 27748 KB Output is correct
14 Correct 13 ms 23820 KB Output is correct
15 Correct 14 ms 23920 KB Output is correct
16 Correct 95 ms 41300 KB Output is correct
17 Correct 13 ms 23764 KB Output is correct
18 Correct 13 ms 23736 KB Output is correct
19 Correct 12 ms 23812 KB Output is correct
20 Correct 13 ms 23816 KB Output is correct
21 Correct 13 ms 23764 KB Output is correct
22 Correct 13 ms 23760 KB Output is correct
23 Incorrect 183 ms 52468 KB Solution announced impossible, but it is possible.
24 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 23764 KB Output is correct
2 Correct 13 ms 23696 KB Output is correct
3 Correct 15 ms 23796 KB Output is correct
4 Correct 12 ms 23764 KB Output is correct
5 Correct 13 ms 23764 KB Output is correct
6 Correct 12 ms 23772 KB Output is correct
7 Correct 12 ms 23764 KB Output is correct
8 Correct 13 ms 23764 KB Output is correct
9 Correct 96 ms 41296 KB Output is correct
10 Correct 19 ms 25472 KB Output is correct
11 Correct 50 ms 32964 KB Output is correct
12 Correct 23 ms 26452 KB Output is correct
13 Correct 24 ms 27748 KB Output is correct
14 Correct 13 ms 23820 KB Output is correct
15 Correct 14 ms 23920 KB Output is correct
16 Correct 95 ms 41300 KB Output is correct
17 Correct 12 ms 23764 KB Output is correct
18 Correct 12 ms 23692 KB Output is correct
19 Correct 12 ms 23756 KB Output is correct
20 Correct 327 ms 76724 KB Output is correct
21 Correct 325 ms 65484 KB Output is correct
22 Correct 332 ms 65624 KB Output is correct
23 Correct 258 ms 61876 KB Output is correct
24 Correct 89 ms 36924 KB Output is correct
25 Correct 130 ms 39096 KB Output is correct
26 Correct 124 ms 39152 KB Output is correct
27 Correct 233 ms 57436 KB Output is correct
28 Correct 235 ms 57316 KB Output is correct
29 Correct 255 ms 58108 KB Output is correct
30 Incorrect 152 ms 39492 KB Solution announced impossible, but it is possible.
31 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 23764 KB Output is correct
2 Correct 13 ms 23696 KB Output is correct
3 Correct 15 ms 23796 KB Output is correct
4 Correct 12 ms 23764 KB Output is correct
5 Correct 13 ms 23764 KB Output is correct
6 Correct 12 ms 23772 KB Output is correct
7 Correct 12 ms 23764 KB Output is correct
8 Correct 13 ms 23764 KB Output is correct
9 Correct 96 ms 41296 KB Output is correct
10 Correct 19 ms 25472 KB Output is correct
11 Correct 50 ms 32964 KB Output is correct
12 Correct 23 ms 26452 KB Output is correct
13 Correct 24 ms 27748 KB Output is correct
14 Correct 13 ms 23820 KB Output is correct
15 Correct 14 ms 23920 KB Output is correct
16 Correct 95 ms 41300 KB Output is correct
17 Correct 281 ms 67396 KB Output is correct
18 Incorrect 241 ms 59648 KB Solution announced impossible, but it is possible.
19 Halted 0 ms 0 KB -

Subtask #6
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 23764 KB Output is correct
2 Correct 13 ms 23696 KB Output is correct
3 Correct 15 ms 23796 KB Output is correct
4 Correct 12 ms 23764 KB Output is correct
5 Correct 13 ms 23764 KB Output is correct
6 Correct 12 ms 23772 KB Output is correct
7 Correct 12 ms 23764 KB Output is correct
8 Correct 13 ms 23764 KB Output is correct
9 Correct 96 ms 41296 KB Output is correct
10 Correct 19 ms 25472 KB Output is correct
11 Correct 50 ms 32964 KB Output is correct
12 Correct 23 ms 26452 KB Output is correct
13 Correct 24 ms 27748 KB Output is correct
14 Correct 13 ms 23820 KB Output is correct
15 Correct 14 ms 23920 KB Output is correct
16 Correct 95 ms 41300 KB Output is correct
17 Correct 13 ms 23764 KB Output is correct
18 Correct 13 ms 23736 KB Output is correct
19 Correct 12 ms 23812 KB Output is correct
20 Correct 13 ms 23816 KB Output is correct
21 Correct 13 ms 23764 KB Output is correct
22 Correct 13 ms 23760 KB Output is correct
23 Incorrect 183 ms 52468 KB Solution announced impossible, but it is possible.
24 Halted 0 ms 0 KB -