目录
一、题目
1、题目描述
2、输入输出
2.1输入
2.2输出
3、原题链接
二、解题报告
1、思路分析
2、复杂度
3、代码详解
一、题目
1、题目描述
2、输入输出
2.1输入
2.2输出
3、原题链接
761E - Dasha and Puzzle
二、解题报告
1、思路分析
如果一个点的度 > 4,那么无解
注意到 平面很大——1e18,而点数 & 边数很小
我们像玩贪吃蛇那样蛇形顺时针内卷的走,如何保证走n - 1次得到的边都不交叉?
我们可以让第一根很长,后面依次减半
基于上面的策略,我们可以这样构造:
从0开始bfs 往外向邻接点伸边,每条边长度为 2^28
第二层的点分别向临界点伸边,每条边长度为 2^27,只要方向不往回走,就不会交叉
……
这样就完成了构造
2、复杂度
时间复杂度: O(N)空间复杂度:O(N)
3、代码详解
#include <bits/stdc++.h>// #define DEBUGusing u32 = unsigned;
using i64 = long long;
using u64 = unsigned long long;constexpr int P = 1E9 + 7;
constexpr int inf32 = 1E9 + 7;
constexpr i64 inf64 = 1E18 + 7;constexpr int N = 2E5;void solve() {int n;std::cin >> n;std::vector<std::vector<int>> adj(n);for (int i = 1, u, v; i < n; ++ i) {std::cin >> u >> v;-- u, -- v;adj[u].push_back(v);adj[v].push_back(u);if (adj[u].size() == 5 || adj[v].size() == 5) {std::cout << "NO\n";return;}}std::vector<bool> vis(n);std::vector<std::pair<int, int>> ans(n);ans[0] = {0, 0};vis[0] = true;constexpr int dir[]{ -1, 0, 1, 0, -1 };std::queue<std::tuple<int, int, int>> q;q.emplace(0, -1, 1 << 29);while (q.size()) {auto [u, d, len] = q.front();q.pop();len /= 2;int curd = 0;for (int v : adj[u]) {if (vis[v]) continue;if (curd == d)++ curd;int x = ans[u].first + dir[curd] * len, y = ans[u].second + dir[curd + 1] * len;ans[v] = {x, y};vis[v] = true;q.emplace(v, curd ^ 2, len);++ curd;}}std::cout << "YES\n";for (auto &[x, y] : ans)std::cout << x << ' ' << y << '\n';}int main() {std::ios::sync_with_stdio(false);std::cin.tie(nullptr);#ifdef DEBUGint cur = clock();freopen("in.txt", "r", stdin);freopen("out.txt", "w", stdout);
#endifint t = 1;// std::cin >> t;while (t--) {solve();}
#ifdef DEBUGstd::cerr << "run-time: " << clock() - cur << '\n';
#endifreturn 0;
}