Submission #439827

#	Time	Username	Problem	Language	Result	Execution time	Memory
439827		humbertoyusta	Fountain Parks (IOI21_parks)	C++17	0 / 100	326 ms	44456 KiB

parks

#include "parks.h"
#include<bits/stdc++.h>
#define f first
#define s second
#define ii pair<int,int>
using namespace std;
#define maxn 200010
#define db(x) cerr<<#x<<": "<<(x)<<"\n";

int mx[4] = { 0 , 2 , 0 , -2 };
int my[4] = { 2 , 0 , -2 , 0 };
int vis[maxn];
ii arr[maxn];
map<ii,int> mk;
vector<int> U, V, A, B;
map<ii,int> mp;

bool add_edge(int u,int v,int plus_){
    U.push_back(u);
    V.push_back(v);
    if( arr[u].f != arr[v].f ){
        if( mk[{(arr[u].f+arr[v].f)/2,arr[u].s + plus_}] ) return false;
        A.push_back( (arr[u].f+arr[v].f)/2 );
        B.push_back( arr[u].s + plus_ );
        mk[{(arr[u].f+arr[v].f)/2,arr[u].s + plus_}] = true;
    }
    else{
        if( mk[{arr[u].f + plus_,(arr[u].s+arr[v].s)/2}] ) return false;
        A.push_back( arr[u].f + plus_ );
        B.push_back( (arr[u].s+arr[v].s)/2 );
        mk[{arr[u].f + plus_,(arr[u].s+arr[v].s)/2}] = true;
    }
    return true;
}

void dfs(int u,int p,int plus_){
    vis[u] = 1;
    for(int i=0; i<4; i++){
        int nx = arr[u].f + mx[i];
        int ny = arr[u].s + my[i];
        if( mp[{nx,ny}] ){
            int v = mp[{nx,ny}] - 1;
            if( vis[v] ) continue;

            int gp = p / 2 * 2 + ( p + 1 ) % 2;
            int nplus = plus_;
            if( i != gp ) nplus *= -1;

            if( add_edge(u,v,nplus) )
                dfs(v,i,nplus);
        }
    }
}

int construct_roads(std::vector<int> x, std::vector<int> y) {
//    if (x.size() == 1) {
//        vector<int> pra;
//        build(pra, pra, pra, pra);
//        return 1;
//    }

    int n = x.size();

    pair<ii,int> st = { { 2000000007 , 2000000007 } , -1 };
    for(int i=0; i<n; i++){
        arr[i] = {x[i],y[i]};
        mp[{x[i],y[i]}] = i + 1;
        st = min( st , { arr[i] , i } );
    }

    int u = st.s;
    vis[u] = 1;
    for(int i=0; i<4; i++){
        int nx = arr[0].f + mx[i];
        int ny = arr[0].s + my[i];
        if( mp[{nx,ny}] ){
            int v = mp[{nx,ny}] - 1;
            if( vis[v] ) continue;
            int plus_ = ( i == 1 ) + ( i == 2 ) - ( i == 0 ) - ( i == 3 );
            add_edge(u,v,plus_);
            dfs(v,i,plus_);
        }
    }

    for(int i=0; i<n; i++)
        if( vis[i] == 0 )
            return 0;

    build(U, V, A, B);
    return 1;
}

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