oj.uz

Submission #609805

# Submission time Handle Problem Language Result Execution time Memory
609805 2022-07-27T22:48:59 Z StrawHatWess Fountain Parks (IOI21_parks) C++17
0 / 100
 113 ms 58308 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+10;


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; 
map<int,int>pos[MX], vis[MX]; 
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]; 
}

int construct_roads(vi X, vi Y) {
    ::X=X; ::Y=Y; 

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

    FOR(i,0,N) 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 'void unionSet(int, int)':
parks.cpp:45:14: warning: suggest parentheses around assignment used as truth value [-Wparentheses]
   45 |     if(rnk[u]=rnk[v]) rnk[u]++;
parks.cpp: In function 'bool cmp(pi, pi)':
parks.cpp:57:33: warning: unused variable 'l' [-Wunused-variable]
   57 |     int i=a.fi, j=a.se, k=b.fi, l=b.se;
      |                                 ^

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 20564 KB Output is correct
2 Correct 11 ms 20676 KB Output is correct
3 Correct 10 ms 20656 KB Output is correct
4 Correct 9 ms 20556 KB Output is correct
5 Correct 10 ms 20564 KB Output is correct
6 Correct 11 ms 20672 KB Output is correct
7 Correct 10 ms 20604 KB Output is correct
8 Correct 12 ms 20564 KB Output is correct
9 Runtime error 113 ms 58308 KB Execution killed with signal 11
10 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 20564 KB Output is correct
2 Correct 11 ms 20676 KB Output is correct
3 Correct 10 ms 20656 KB Output is correct
4 Correct 9 ms 20556 KB Output is correct
5 Correct 10 ms 20564 KB Output is correct
6 Correct 11 ms 20672 KB Output is correct
7 Correct 10 ms 20604 KB Output is correct
8 Correct 12 ms 20564 KB Output is correct
9 Runtime error 113 ms 58308 KB Execution killed with signal 11
10 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 20564 KB Output is correct
2 Correct 11 ms 20676 KB Output is correct
3 Correct 10 ms 20656 KB Output is correct
4 Correct 9 ms 20556 KB Output is correct
5 Correct 10 ms 20564 KB Output is correct
6 Correct 11 ms 20672 KB Output is correct
7 Correct 10 ms 20604 KB Output is correct
8 Correct 12 ms 20564 KB Output is correct
9 Runtime error 113 ms 58308 KB Execution killed with signal 11
10 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 20564 KB Output is correct
2 Correct 11 ms 20676 KB Output is correct
3 Correct 10 ms 20656 KB Output is correct
4 Correct 9 ms 20556 KB Output is correct
5 Correct 10 ms 20564 KB Output is correct
6 Correct 11 ms 20672 KB Output is correct
7 Correct 10 ms 20604 KB Output is correct
8 Correct 12 ms 20564 KB Output is correct
9 Runtime error 113 ms 58308 KB Execution killed with signal 11
10 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 20564 KB Output is correct
2 Correct 11 ms 20676 KB Output is correct
3 Correct 10 ms 20656 KB Output is correct
4 Correct 9 ms 20556 KB Output is correct
5 Correct 10 ms 20564 KB Output is correct
6 Correct 11 ms 20672 KB Output is correct
7 Correct 10 ms 20604 KB Output is correct
8 Correct 12 ms 20564 KB Output is correct
9 Runtime error 113 ms 58308 KB Execution killed with signal 11
10 Halted 0 ms 0 KB -

Subtask #6
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 20564 KB Output is correct
2 Correct 11 ms 20676 KB Output is correct
3 Correct 10 ms 20656 KB Output is correct
4 Correct 9 ms 20556 KB Output is correct
5 Correct 10 ms 20564 KB Output is correct
6 Correct 11 ms 20672 KB Output is correct
7 Correct 10 ms 20604 KB Output is correct
8 Correct 12 ms 20564 KB Output is correct
9 Runtime error 113 ms 58308 KB Execution killed with signal 11
10 Halted 0 ms 0 KB -