# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
865436 |
2023-10-24T08:23:32 Z |
boris_mihov |
Roads (CEOI20_roads) |
C++17 |
|
573 ms |
524288 KB |
#include <algorithm>
#include <iostream>
#include <numeric>
#include <cassert>
#include <vector>
#include <random>
#include <queue>
#include <stack>
#include <set>
typedef long long llong;
const int MAXN = 200000 + 10;
const int MOD = 1e9 + 7;
const int INF = 2e9;
int n;
struct DSU
{
int par[MAXN];
int dep[MAXN];
void build()
{
std::iota(par + 1, par + 1 + 2 * n, 1);
std::fill(dep + 1, dep + 1 + 2 * n, 1);
}
int find(int node)
{
if (par[node] == node) return node;
return par[node] = find(par[node]);
}
void connect(int u, int v)
{
u = find(u);
v = find(v);
assert(u != v);
if (dep[u] > dep[v])
{
std::swap(u, v);
}
if (dep[u] == dep[v])
{
dep[v]++;
}
par[u] = v;
}
bool areConnected(int u, int v)
{
return find(u) == find(v);
}
};
DSU dsu;
struct Point
{
llong x, y;
};
llong dist(Point a, Point b)
{
return abs(a.x - b.x);
}
Point p[MAXN];
std::mt19937 rng(69420);
void solve()
{
dsu.build();
for (int i = 1 ; i <= n ; ++i)
{
dsu.connect(i, n + i);
}
std::vector <std::pair <Point,Point>> answer;
std::vector <std::pair <int,int>> mst;
mst.reserve(n * n * 4);
for (int i = 1 ; i <= 2 * n ; ++i)
{
for (int j = 1 ; j <= 2 * n ; ++j)
{
// int curr = rng() % (2 * n) + 1;
if (abs(i - j) % n == 0) continue;
mst.push_back({i, j});
}
}
std::sort(mst.begin(), mst.end(), [&](auto p1, auto p2)
{
return dist(p[p1.first], p[p1.second]) < dist(p[p2.first], p[p2.second]);
});
for (const auto &[x, y] : mst)
{
if (dsu.areConnected(x, y))
{
continue;
}
answer.push_back({p[x], p[y]});
dsu.connect(x, y);
}
// assert(answer.size() == n - 1);
for (const auto &[p1, p2] : answer)
{
std::cout << p1.x << ' ' << p1.y << ' ' << p2.x << ' ' << p2.y << '\n';
}
}
void input()
{
std::cin >> n;
for (int i = 1 ; i <= n ; ++i)
{
std::cin >> p[i].x >> p[i].y >> p[n + i].x >> p[n + i].y;
}
}
void fastIOI()
{
std::ios_base :: sync_with_stdio(0);
std::cout.tie(nullptr);
std::cin.tie(nullptr);
}
int main()
{
fastIOI();
input();
solve();
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
2392 KB |
Output is correct |
2 |
Runtime error |
573 ms |
524288 KB |
Execution killed with signal 9 |
3 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
2392 KB |
Output is correct |
2 |
Correct |
17 ms |
3788 KB |
Output is correct |
3 |
Failed |
502 ms |
34076 KB |
Condition failed: "pf == Sline.end() || !Cross(S[*pi], S[*pf])" |
4 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
2392 KB |
Output is correct |
2 |
Correct |
17 ms |
3676 KB |
Output is correct |
3 |
Failed |
499 ms |
33872 KB |
Condition failed: "pf == Sline.end() || !Cross(S[*pi], S[*pf])" |
4 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
2392 KB |
Output is correct |
2 |
Correct |
17 ms |
3676 KB |
Output is correct |
3 |
Failed |
497 ms |
33816 KB |
Condition failed: "pf == Sline.end() || !Cross(S[*pi], S[*pf])" |
4 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
2396 KB |
Output is correct |
2 |
Correct |
1 ms |
2396 KB |
Output is correct |
3 |
Correct |
17 ms |
3788 KB |
Output is correct |
4 |
Failed |
500 ms |
33824 KB |
Condition failed: "pf == Sline.end() || !Cross(S[*pi], S[*pf])" |
5 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
2392 KB |
Output is correct |
2 |
Runtime error |
570 ms |
524288 KB |
Execution killed with signal 9 |
3 |
Halted |
0 ms |
0 KB |
- |