제출 #599984

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
599984		Valaki2	분수 공원 (IOI21_parks)	C++17	5 / 100	500 ms	57540 KiB

parks

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

#define x X
#define y Y

#define pb push_back
#define mp make_pair
#define pii pair<int, int>
#define fi first
#define se second

const int maxn = 2e5;
const vector<pii > directions = {mp(-2, 0), mp(0, -2), mp(0, 2), mp(2, 0)};

bool check_possibility(int n, vector<int> x, vector<int> y) {
    unordered_map<int, unordered_map<int, bool> > m;
    unordered_map<int, unordered_map<int, int> > f;
    for(int i = 0; i < n; i++) {
        f[x[i]][y[i]] = i + 1;
    }
    queue<int> q;
    q.push(0);
    m[x[0]][y[0]] = true;
    int cnt = 0;
    while(!q.empty()) {
        int cur = q.front();
        q.pop();
        cnt++;
        for(pii dir : directions) {
            pii new_point = mp(x[cur] + dir.fi, y[cur] + dir.se);
            if(f[new_point.fi][new_point.se] && !m[new_point.fi][new_point.se]) {
                m[new_point.fi][new_point.se] = true;
                int new_id = f[new_point.fi][new_point.se] - 1;
                q.push(new_id);
            }
        }
    }
    return (cnt == n);
}

struct fountain {
    int x, y, id;
    fountain() : x(0), y(0), id(-1) {}
    fountain(int x_, int y_, int id_) :
        x(x_), y(y_), id(id_) {}
};

int n;
vector<fountain > points;
vector<int> x;
vector<int> y;
unordered_map<int, unordered_map<int, int> > fountain_at;

unordered_map<int, unordered_map<int, bool> > bench_at;
vector<int> ans_u;
vector<int> ans_v;
vector<int> ans_a;
vector<int> ans_b;

void build_road_bench(int road_u, int road_v, pii bench_pos) {
    ans_u.pb(road_u);
    ans_v.pb(road_v);
    ans_a.pb(bench_pos.fi);
    ans_b.pb(bench_pos.se);
    bench_at[bench_pos.fi][bench_pos.se] = true;
}

vector<fountain> by_a;
vector<fountain> by_b;
vector<fountain> by_c;

bool sort_by_y(const fountain &a, const fountain &b) {
    return a.y < b.y;
}

void solve() {
    /*for(fountain p : points) {
        if(p.x == 2) {
            by_a.pb(p);
        }
        if(p.x == 4) {
            by_b.pb(p);
        }
        if(p.x == 6) {
            by_c.pb(p);
        }
    }
    sort(by_a.begin(), by_a.end(), sort_by_y);
    sort(by_b.begin(), by_b.end(), sort_by_y);
    sort(by_c.begin(), by_c.end(), sort_by_y);*/
    // type A and E
    for(int i = 2; i <= maxn; i += 2) {
        int a = fountain_at[2][i], b = fountain_at[2][i + 2];
        if(a && b) {
            build_road_bench(a - 1, b - 1, mp(1, i + 1));
        }
        a = fountain_at[6][i], b = fountain_at[6][i + 2];
        if(a && b) {
            build_road_bench(a - 1, b - 1, mp(7, i + 1));
        }
    }
    // type B
    for(int i = 2; i <= maxn; i += 2) {
        int a = fountain_at[2][i], b = fountain_at[2][i + 2],
            c = fountain_at[4][i], d = fountain_at[4][i + 2];
        if((b && d) && (!a || !c)) {
            build_road_bench(b - 1, d - 1, mp(3, i + 1));
        }
    }
    // type C
    for(int i = 2; i <= maxn; i += 2) {
        int a = fountain_at[4][i], b = fountain_at[4][i + 2];
        if(a && b) {
            if(!bench_at[3][i + 1]) {
                build_road_bench(a - 1, b - 1, mp(3, i + 1));
            } else {
                build_road_bench(a - 1, b - 1, mp(5, i + 1));
            }
        }
    }
    // type D
    for(int i = 2; i <= maxn; i += 2) {
        int a = fountain_at[4][i], b = fountain_at[4][i + 2],
            c = fountain_at[6][i], d = fountain_at[6][i + 2];
        if((b && d) && (!a || !c)) {
            if(!bench_at[5][i + 1]) {
                build_road_bench(b - 1, d - 1, mp(5, i + 1));
            } else {
                build_road_bench(b - 1, d - 1, mp(5, i + 3));
            }
        }
    }
}

#undef x
#undef y
int construct_roads(vector<int> x, vector<int> y) {
    // edge case
    if (x.size() == 1) {
        build({}, {}, {}, {});
        return 1;
    }
    // sample solution
    /*vector<int> u, v, a, b;
    u.push_back(0);
    v.push_back(1);
    a.push_back(x[0]+1);
    b.push_back(y[0]-1);
    build(u, v, a, b);*/
    n = x.size();
    if(!check_possibility(n, x, y)) {
        return 0;
    }
    X = x;
    Y = y;
    points.assign(n, fountain());
    for(int i = 0; i < n; i++) {
        points[i] = fountain(x[i], y[i], i);
        fountain_at[x[i]][y[i]] = i + 1;
    }
    solve();
    // build solution
    build(ans_u, ans_v, ans_a, ans_b);
    return 1;
}

/*
5
4 4
4 6
6 4
4 2
2 4
*/

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