제출 #436800

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
436800		humbertoyusta	분수 공원 (IOI21_parks)	C++17	45 / 100	641 ms	77852 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];
vector<int> U, V, A, B;
map<ii,int> mp;

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

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;

            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();

    for(int i=0; i<n; i++){
        arr[i] = {x[i],y[i]};
        mp[{x[i],y[i]}] = i + 1;
    }

    int u = 0;
    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: 5 / 5
• Subtask 2: 0 / 10
• Subtask 3: 0 / 15
• Subtask 4: 20 / 20
• Subtask 5: 20 / 20
• Subtask 6: 0 / 30