| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 1245324 | sano | 분수 공원 (IOI21_parks) | C++20 | 0 ms | 0 KiB |
//#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] });
}
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;
}*/