Codeforce 761E Dasha and Puzzle(构造)

 1 #include <bits/stdc++.h>
 2 
 3 using namespace std;
 4 
 5 #define REP(i,n)                for(int i(0); i <  (n); ++i)
 6 #define rep(i,a,b)              for(int i(a); i <= (b); ++i)
 7 #define LL              long long
 8 #define PB              push_back
 9 
10 const int Q     = 1000        +       10;
11 const int A    = 30          +       1;
12 const LL dx[]     = {0, 1, 0, -1};
13 const LL dy[]     = {1, 0, -1, 0};
14 
15 struct node{ LL x, y;} c[A];
16 vector <int> v[A];
17 int f[A][A];
18 LL num[Q];
19 int n;
20 int x, y;
21 int inn[Q];
22 bool vis[Q];
23 
24 void dfs(int x, int cnt){
25     REP(i, (int)v[x].size()){
26         int u = v[x][i];
27         if (!vis[u]){
28             vis[u] = true;
29             REP(j, 4){
30                 if (!f[x][j] && !f[u][(j + 2) % 4]){
31                     c[u].x = c[x].x + dx[j] * num[cnt];
32                     c[u].y = c[x].y + dy[j] * num[cnt];
33                     f[u][(j + 2) % 4] = 1;
34                     f[x][j] = 1;
35                     break;
36                 }
37             }
38             dfs(u, cnt - 1);
39         }
40     }
41 }    
42 
43 int main(){
44 
45     num[0] = 1; rep(i, 1, 36) num[i] = num[i - 1] * 2;
46     scanf("%d", &n);
47     rep(i, 1, n - 1){
48         scanf("%d%d", &x, &y);
49         v[x].PB(y);
50         v[y].PB(x);
51         ++inn[x], ++inn[y];
52     }
53 
54     rep(i, 1, n) if (inn[i] > 4){
55         puts("NO");
56         return 0;
57     }
58 
59     memset(vis, false, sizeof vis); vis[1] = true;
60     c[1].x = c[1].y = 0;
61     dfs(1, 30);
62 
63     puts("YES");
64     rep(i, 1, n){
65         printf("%lld %lld\n", c[i].x, c[i].y);
66     }
67 
68     return 0;
69 
70 }