제출 #479199

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
479199		couplefire	분수 공원 (IOI21_parks)	C++17	45 / 100	1220 ms	48208 KiB

parks

#include "parks.h"
#include <bits/stdc++.h>
using namespace std;
#define pii pair<int, int>
#define f first
#define s second

int n, m;
vector<pii> pts, sqrs;
map<pii, int> pid, sid;
vector<int> fa, u_ans, v_ans, a_ans, b_ans;
vector<vector<pair<int, pii>>> adj;
vector<bool> vis;
set<pii> roads;

int find(int v){return v==fa[v]?v:fa[v]=find(fa[v]);}

void unite(int u, int v){
    u = find(u), v = find(v);
    if(u==v) return;
    fa[u] = v;
}

pii get(pii a, pii b){
    if(a.f==b.f){
        if(a.s>b.s) swap(a, b);
        int x = pid[{a.f-1, a.s+1}], y = pid[{a.f+1, a.s+1}];
        if(x>y) swap(x, y);
        return {x, y};
    }
    if(a.f>b.f) swap(a, b);
    int x = pid[{a.f+1, a.s+1}], y = pid[{a.f+1, a.s-1}];
    if(x>y) swap(x, y);
    return {x, y};
}

bool horz(pii a){
    return ((a.f+a.s)/2)&1;
}

void dfs(int v){
    vis[v] = 1;
    for(auto u : adj[v])
        if(!vis[u.f]) roads.erase(u.s), dfs(u.f);
}

int construct_roads(vector<int> _x, vector<int> _y){
    n = _x.size();
    for(int i = 0; i<n; ++i)
        pts.push_back({_x[i], _y[i]}), pid[pts.back()] = i;
    fa.resize(n);
    iota(fa.begin(), fa.end(), 0);
    for(int i = 0; i<n; ++i){
        pii npt = {pts[i].f+2, pts[i].s};
        if(pid.count(npt)) unite(i, pid[npt]);
        npt = {pts[i].f, pts[i].s+2};
        if(pid.count(npt)) unite(i, pid[npt]);       
    }
    for(int i = 1; i<n; ++i)
        if(find(0)!=find(i)) return 0;
    for(int i = 0; i<n; ++i){
        pii ap = {pts[i].f+2, pts[i].s}, bp = {pts[i].f, pts[i].s+2};
        if(pid.count(ap)) roads.insert({min(i, pid[ap]), max(i, pid[ap])});
        if(pid.count(bp)) roads.insert({min(i, pid[bp]), max(i, pid[bp])});
    }
    for(int i = 0; i<n; ++i){
        pii bl = pts[i], br = {bl.f+2, bl.s}, tl = {bl.f, bl.s+2}, tr = {bl.f+2, bl.s+2};
        if(pid.count(bl) && pid.count(br) && pid.count(tl) && pid.count(tr))
            sqrs.push_back({bl.f+1, bl.s+1}), sid[sqrs.back()] = (int)sqrs.size()-1;
    }
    m = (int)sqrs.size();
    adj.resize(m+1);
    vis.assign(m+1, 0);
    for(int i = 0; i<m; ++i){
        pii as, bs;
        if(horz(sqrs[i]))
            as = {sqrs[i].f+2, sqrs[i].s}, bs = {sqrs[i].f-2, sqrs[i].s};
        else as = {sqrs[i].f, sqrs[i].s+2}, bs = {sqrs[i].f, sqrs[i].s-2};
        if(sid.count(as)) adj[i].push_back({sid[as], get(sqrs[i], as)});
        if(sid.count(bs)) adj[i].push_back({sid[bs], get(sqrs[i], bs)});
        pii cs, ds;
        if(((sqrs[i].f+sqrs[i].s)/2)&1)
            cs = {sqrs[i].f, sqrs[i].s+2}, ds = {sqrs[i].f, sqrs[i].s-2};
        else cs = {sqrs[i].f+2, sqrs[i].s}, ds = {sqrs[i].f-2, sqrs[i].s};
        if(!sid.count(cs)) adj[m].push_back({i, get(sqrs[i], cs)});
        if(!sid.count(ds)) adj[m].push_back({i, get(sqrs[i], ds)});
    } dfs(m);
    for(auto [x, y] : roads){
        u_ans.push_back(x), v_ans.push_back(y);
        pii a = pts[x], b = pts[y];
        if(a.f==b.f){
            if(a.s>b.s) swap(a, b);
            if(horz({a.f-1, a.s+1})) a_ans.push_back(a.f-1), b_ans.push_back(a.s+1);
            else a_ans.push_back(a.f+1), b_ans.push_back({a.s+1});
        } else{
            if(a.f>b.f) swap(a, b);
            if(!horz({a.f+1, a.s-1})) a_ans.push_back(a.f+1), b_ans.push_back(a.s-1);
            else a_ans.push_back(a.f+1), b_ans.push_back(a.s+1);
        }
    }
    build(u_ans, v_ans, a_ans, b_ans);
    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