제출 #1245333

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1245333		sano	분수 공원 (IOI21_parks)	C++20	30 / 100	1161 ms	60124 KiB

parks

#include "parks.h"
#include<iostream>
#include<vector>
#include<queue>
#include<deque>
#include<string>
#include<fstream>
#include<algorithm>
#include <iomanip>
#include<map>
#include <set>
#include <unordered_map>
#include <stack>
#include <unordered_set>
#include <cmath>
#include <cstdint>
#include <cassert>
#include <bitset>
#include <random>
#include <chrono>
#include <cstring>
#include <variant>
#define shit short int
#define ll long long
#define ld long double
//#define int ll
#define For(i, n) for(int i = 0; i < (int)n; i++)
#define ffor(i, a, n) for(int i = (int)a; i < (int)n; i++)
#define rfor(i, n) for(int i = (int)n; i >= (int)0; i--)
#define rffor(i, a, n) for(int i = (int)n; i >= (int)a; i--)
#define vec vector
#define ff first
#define ss second
#define pb push_back
#define pii pair<int, int>
#define pld pair<ld, ld>
#define NEK 200000000000000
#define mod 1000000007
#define mod2 1000000009
#define rsz resize 
#define prv 43
#define prv2 47
#define D 8
#define trav(a,x) for (auto& a: x)
#define pb push_back
#define ub upper_bound
#define lb lower_bound
#define all(x) (x).begin(), (x).end()
#define sig 0.0000001

using namespace std;

vec<pii> r = { {-2, 0}, {2, 0}, {0, -2}, {0, 2} };
/*
void build(vec<int> u, vec<int> v, vec<int> a, vec<int> b) {
    set<pii> s;
    int n = u.size();
    For(i, n) {
        if (s.find({ a[i], b[i] }) != s.end()) {
            cout << "pokazilo_sa\n" << endl;
            return;
        }
        s.insert({ a[i], b[i] });
    }
    For(i, n) {
        cout << u[i] << ' ' << v[i] << ' ' << a[i] << ' ' << b[i] << '\n';
    }
    return;
}*/

int otec(int x, vec<int>& o) {
    if (o[x] < 0) return x;
    o[x] = otec(o[x], o);
    return o[x];
}

void spoj(int a, int b, vec<int>&o) {
    a = otec(a, o), b = otec(b, o);
    if (a == b) return;
    if (o[a] > o[b]) swap(a, b);
    o[a] += o[b];
    o[b] = a;
    return;
}

bool kontrola(vec<int>& x, vec<int>& y) {
    int n = x.size();
    vec<pii> h;
    map<pii, int> umap;
    For(i, n) {
        umap[{x[i], y[i]}] = i;
    }
    For(i, n) {
        for (auto& j : r) {
            int nx = j.ff + x[i];
            int ny = j.ss + y[i];
            if (umap.find({ nx, ny }) == umap.end()) continue;
            if (i > umap[{nx, ny}]) continue;
            h.push_back({ i, umap[{nx, ny}] });
        }
    }
    vec<pii> bb;
    vec<int> o(n, -1);
    For(i, h.size()) {
        spoj(h[i].ff, h[i].ss, o);
    }
    int mojo = otec(0, o);
    if ((o[mojo] * (-1)) != n) {
        return 1;
    }
    return 0;
}

int construct_roads(vec<int> x, vec<int> y) {
    int n = x.size();
    int maxx = 0;
    For(i, n) {
        maxx = max(maxx, x[i]);
    }
    if (kontrola(x, y)) return 0;
    if (maxx == 4) {
        vec<pii> h;
        map<pii, int> umap;
        For(i, n) {
            umap[{x[i], y[i]}] = i;
        }
        For(i, n) {
            for (auto& j : r) {
                int nx = j.ff + x[i];
                int ny = j.ss + y[i];
                if (umap.find({ nx, ny }) == umap.end()) continue;
                if (i > umap[{nx, ny}]) continue;
                h.push_back({ i, umap[{nx, ny}] });
            }
        }
        vec<pii> bb;
        vec<int> o(n, -1);
        For(i, h.size()) {
            spoj(h[i].ff, h[i].ss, o);
            if (x[h[i].ff] == x[h[i].ss]) {
                if (x[h[i].ff] == 2) {
                    bb.push_back({ x[h[i].ff] - 1, min(y[h[i].ss] + 1, y[h[i].ff] + 1) });
                }
                if (x[h[i].ss] == 4) {
                    bb.push_back({ x[h[i].ff] + 1, min(y[h[i].ss] + 1, y[h[i].ff] + 1) });
                }
            }
            else {
                bb.push_back({ min(x[h[i].ss] + 1, x[h[i].ff] + 1), y[h[i].ff] - 1 });
            }
        }
        int mojo = otec(0, o);
        if ((o[mojo] * (-1)) != n) {
            return 0;
        }
        vec<int> u, v, a, b;
        For(i, h.size()) {
            u.push_back(h[i].ff);
            v.push_back(h[i].ss);
            a.push_back(bb[i].ff);
            b.push_back(bb[i].ss);
        }
        build(u, v, a, b);
        return 1;
    }
    else {
        map<pii, int> umap;
        set<pii> h;
        vec<vec<pii>> kat(3);
        For(i, n) {
            int nx = x[i] / 2 - 1;
            kat[nx].push_back({ y[i], i });
        }
        For(i, kat.size()) sort(all(kat[i]));
        For(i, n) {
            umap[{x[i], y[i]}] = i;
        }
        int pos = -1;
        for(auto i : kat[2]) {
            if (i.ff > (pos + 2)) {
                pos = i.ff;
                if (umap.find({ 4, i.ff }) == umap.end()) continue;
                h.insert({ min(umap[{ 4, i.ff }], i.ss), max(umap[{ 4, i.ff }], i.ss) });
            }
            else {
                pos = i.ff;
                h.insert({ min(umap[{ 6, i.ff - 2 }], i.ss), max(umap[{ 6, i.ff - 2 }], i.ss) });
            }
        }
        pos = -1;
        for(auto i : kat[1]) {
            if (i.ff > (pos + 2)) {
                pos = i.ff;
                if (umap.find({ 2, i.ff }) != umap.end()) {
                    h.insert({ min(umap[{ 2, i.ff }], i.ss), max(umap[{ 2, i.ff }], i.ss) });
                }
                if (umap.find({ 6, i.ff }) != umap.end()) {
                    h.insert({ min(umap[{ 6, i.ff }], i.ss), max(umap[{ 6, i.ff }], i.ss) });
                }
            }
            else {
                pos = i.ff;
                h.insert({min(umap[{ 4, i.ff - 2 }], i.ss), max(umap[{ 4, i.ff - 2 }], i.ss)});
            }
        }
        pos = -1;
        for (auto i : kat[0]) {
            if (i.ff > (pos + 2)) {
                pos = i.ff;
                if (umap.find({ 4, i.ff }) == umap.end()) continue;
                h.insert({ min(umap[{ 4, i.ff }], i.ss), max(umap[{ 4, i.ff }], i.ss) });
            }
            else {
                pos = i.ff;
                h.insert({ min(umap[{ 2, i.ff - 2 }], i.ss), max(umap[{ 2, i.ff - 2 }], i.ss) });
            }
        }
        map<pii, int> bb;
        int ind = 0;
        for (auto i : h) {
            int a = i.ff, b = i.ss;
            if ((x[a] == 6 && x[b] == 4) || (x[a] == 4 && x[b] == 6)) {
                bb[{ 5, y[a] - 1 }] = ind;
            }
            ind++;
        }
        ind = 0;
        for (auto i : h) {
            int a = i.ff, b = i.ss;
            if (x[a] == x[b]) {
                if (x[a] == 6) {
                    bb[{7, min(y[a] + 1, y[b] + 1)}] = ind;
                }
                if (x[a] == 2) {
                    bb[{1, min(y[a] + 1, y[b] + 1)}] = ind;
                }
                if (x[a] == 4) {
                    int x1 = 5, y1 = min(y[a] + 1, y[b] + 1);
                    if (bb.find({ x1, y1 }) == bb.end()) {
                        bb[{x1, y1}] = ind;
                    }
                    else {
                        bb[{x1 - 2, y1}] = ind;
                    }
                }
            }
            ind++;
        }
        ind = 0;
        for (auto i : h) {
            int a = i.ff, b = i.ss;
            if ((x[a] == 4 && x[b] == 2) || (x[a] == 2 && x[b] == 4)) {
                int x1 = 3, y1 = y[a] - 1;
                if (bb.find({ x1, y1 }) == bb.end()) {
                    bb[{x1, y1}] = ind;
                }
                else {
                    bb[{x1, y1 + 2}] = ind;
                }
            }
            ind++;
        }
        vec<int> u, v, a(h.size()), b(h.size());
        for (auto i : h) {
            u.push_back(i.ff);
            v.push_back(i.ss);
        }
        for (auto i : bb) {
            a[i.ss] = i.ff.ff;
            b[i.ss] = i.ff.ss;
        }
        build(u, v, a, b);
        return 1;
    }
    return 1;
}
/*
signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int n; cin >> n;
    vec<int> x(n), y(n);
    For(i, n) cin >> x[i] >> y[i];
    cout << construct_roads(x, y) << '\n';
    return 0;
}*/

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