제출 #550696

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
550696		PiejanVDC	분수 공원 (IOI21_parks)	C++17	0 / 100	359 ms	21624 KiB

parks

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

int dx[4] = {2,-2,0,0};
int dy[4] = {0,0,2,-2};

void build(vector<int> u, vector<int> v, vector<int> a, vector<int> b);

const int mxN = (int)2e5 + 5;

vector<int>parent(mxN);

int UF(int u) {
    if(parent[u] == u) return u;
    return parent[u] = UF(parent[u]);
}

int construct_roads(std::vector<int> x, std::vector<int> y) {
    const int n = (int)x.size();
    for(int i = 0 ; i < n ; i++)
        parent[i] = i;
    set<pair<int,int>>s;
    map<pair<int,int>,int>mp;
    for(int i = 0 ; i < n ; i++)
        mp[{x[i],y[i]}] = i;
    vector<int>u(n-1),v(n-1),a(n-1),b(n-1);
    map<pair<int,int>,bool>processed;

    for(int i = 0 ; i < n ; i++) {
        for(int d = 0 ; d < 4 ; d++) {
            processed[{x[i],y[i]}] = 1;
            if(mp.count({x[i] + dx[d], y[i] + dy[d]})) {
                if(processed[{x[i] + dx[d], y[i] + dy[d]}])
                    continue;
                int f = mp[{x[i] + dx[d], y[i] + dy[d]}];
                if(dx[d] == 0) {
                    if(s.count({x[i]+1,y[i] + dy[d]/2}))
                        a[i] = x[i]-1, b[i] = y[i] + dy[d]/2, u[i] = i, v[i] = f, s.insert({a[i],b[i]}), parent[UF(i)] = UF(f);
                    else
                        a[i] = x[i]+1, b[i] = y[i] + dy[d]/2, u[i] = i, v[i] = f, s.insert({a[i],b[i]}), parent[UF(i)] = UF(f);
                } else {
                    if(s.count({x[i] + dx[d]/2, y[i]+1}))
                        a[i] = x[i] + dx[d]/2, b[i] = y[i]-1, u[i] = i, v[i] = f, s.insert({a[i],b[i]}), parent[UF(i)] = UF(f);
                    else
                        a[i] = x[i] + dx[d]/2, b[i] = y[i]+1, u[i] = i, v[i] = f, s.insert({a[i],b[i]}), parent[UF(i)] = UF(f);
                }
            }
        }
    }
    int cnt = 0;
    for(int i = 0 ; i < n ; i++)
        cnt += parent[i] == i;
    for(int i = 0 ; i < n-1 ; i++) {
        if(a[i] == 0 && b[i] == 0)
            return 0;
    }
    if(cnt > 1)
        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