Codeforces Round #394 (Div. 2) E. Dasha and Puzzle DFS

E. Dasha and Puzzle

链接：

http://codeforces.com/contest/761/problem/E

代码：

 1 #include <iostream>  
 2 #include <vector>  
 3 using namespace std;
 4 
 5 typedef pair<int, int> P;
 6 P ans[50];
 7 vector<int> E[100];
 8 int dx[4] = { 0,1,0,-1 };
 9 int dy[4] = { 1,0,-1,0 };
10 int vis[50];
11 
12 void dfs(int u, int num, int x, int y, int fromdir) {
13     vis[u] = 1;
14     ans[u] = P(x, y);
15     int dir = 0;
16     for (auto i = 0; i < E[u].size(); i++) {
17         int v = E[u][i];
18         if (vis[v]) continue;
19         if (dir == fromdir)    dir++;
20         dfs(v, num - 1, x + (1 << num)*dx[dir], y + (1 << num)*dy[dir], (dir + 2) % 4);
21         dir++;
22     }
23 }
24 int main() {
25     int n;
26     cin >> n;
27     for (int i = 1; i < n; i++) {
28         int u, v;
29         cin >> u >> v;
30         E[u].push_back(v);
31         E[v].push_back(u);
32     }
33     for (int i = 0; i < n; i++) {
34         if (E[i].size()>4) {
35             cout << "NO" << endl;
36             return 0;
37         }
38     }
39     dfs(1, 30, 0, 0, -1);
40     cout << "YES" << endl;
41     for (int i = 1; i <= n; i++) {
42         cout << ans[i].first << " " << ans[i].second << endl;
43     }
44     return 0;
45 }