| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1039921 | yanb | Fountain Parks (IOI21_parks) | C++17 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
using namespace std;
//#define int long long
//#define pii pair<long long, long long>
#define pii pair<int, int>
#define pib pair<int, bool>
#define fi first
#define se second
void build(vector<int> u, vector<int> v, vector<int> a, vector<int> b);
void dfs(int v, vector<vector<int>> &g, vector<bool> &uu) {
if (uu[v]) return;
uu[v] = 1;
for (int u : g[v]) dfs(u, g, uu);
}
void follow(int v, vector<vector<int>> &h, vector<int> &a, vector<int> &b, map<pii, int> &mid,
vector<pii> &pm, vector<int> &x, vector<int> &y) {
if (h[v].empty()) return;
while (h[v].size()){
int u = h[v].back();
//cout << "Erasing " << pm[v].fi << "," << pm[v].se << " ~ " << pm[u].fi << "," << pm[u].se << "\n";
h[v].erase(remove(h[v].begin(), h[v].end(), u), h[v].end());
h[u].erase(remove(h[u].begin(), h[u].end(), v), h[u].end());
int pd = mid[{(pm[v].fi + pm[u].fi) / 2, (pm[v].se + pm[u].se) / 2}];
a[pd] = pm[u].fi;
b[pd] = pm[u].se;
follow(u, h, a, b, mid, pm, x, y);
}
}
int do_tree(vector<int> x, vector<int> y) {
int n = x.size();
map<pii, int> id, mid;
for (int i = 0; i < n; i++) {
id[{x[i], y[i]}] = i;
}
vector<vector<int>> g(n);
for (int i = 0; i < n; i++) {
if (id.count({x[i] + 2, y[i]})) g[i].push_back(id[{x[i] + 2, y[i]}]);
if (id.count({x[i] - 2, y[i]})) g[i].push_back(id[{x[i] - 2, y[i]}]);
if (id.count({x[i], y[i] + 2})) g[i].push_back(id[{x[i], y[i] + 2}]);
if (id.count({x[i], y[i] - 2})) g[i].push_back(id[{x[i], y[i] - 2}]);
}
vector<bool> uu(n);
dfs(0, g, uu);
for (int i = 0; i < n; i++) {
if (!uu[i]) return 0;
}
vector<int> bu, bv;
int cnt = 0;
for (int u = 0; u < n; u++) {
for (int v : g[u]) {
if (v > u) {
bv.push_back(v);
bu.push_back(u);
mid[{(x[v] + x[u]) / 2, (y[v] + y[u]) / 2}] = cnt;
cnt++;
}
}
}
cnt = 0;
map<pii, int> mp;
vector<pii> pm;
vector<vector<int>> h;
for (int v = 0; v < n; v++) {
for (int u : g[v]) {
int xm = (x[v] + x[u]) / 2, ym = (y[v] + y[u]) / 2;
pii p = {xm + (ym - y[v]), ym + (xm - x[v])};
pii q = {xm + (ym - y[u]), ym + (xm - x[u])};
if (!mp.count(p)) {
mp[p] = cnt;
h.push_back({});
pm.push_back(p);
cnt++;
}
if (!mp.count(q)) {
mp[q] = cnt;
h.push_back({});
pm.push_back(q);
cnt++;
}
h[mp[p]].push_back(mp[q]);
}
}
for (int v = 0; v < cnt; ++v) if (h[v].size() > 2) return 0;
// for (int v = 0; v < cnt; ++v) {
// cout << pm[v].first << " " << pm[v].second << "\n";
// std::cout << "Start edges" << "\n";
// for (int to : h[v]) std::cout << to << " ";
// std::cout << "\n";
// }
vector<int> a(n - 1), b(n - 1);
for (int i = 0; i < cnt; i++) {
follow(i, h, a, b, mid, pm, x, y);
}
build(bu, bv, a, b);
return 1;
}
int construct_roads(vector<int> x, vector<int> y) {
return do_tree(x, y);
}
#ifndef ONLINE_JUDGE
void build(vector<int> u, vector<int> v, vector<int> a, vector<int> b) {
int n = u.size();
for (int i = 0; i < n; i++) cout << u[i] << " ";
cout << "\n";
for (int i = 0; i < n; i++) cout << v[i] << " ";
cout << "\n";
for (int i = 0; i < n; i++) cout << a[i] << " ";
cout << "\n";
for (int i = 0; i < n; i++) cout << b[i] << " ";
cout << "\n";
}
signed main() {
construct_roads({2, 2, 4}, {2, 4, 2});
//construct_roads({4, 4, 6, 4, 2}, {4, 6, 4, 2, 4});
}
#endif