Not Assigning(1400)
2022/3/1 23:22:41
本文主要是介绍Not Assigning(1400),对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
1 /**\ 2 https://codeforces.com/contest/1627/problem/C 3 想要满足能够赋值的条件,必须所有点的度都不能>3 4 那么树退化成了链,就op记下输出格式,然后ans记录dfs的结果 5 由于链式 2 3 2 3 就满足prime path 6 \**/ 7 #include <bits/stdc++.h> 8 using namespace std; 9 #define fi first 10 #define se second 11 #define go continue 12 #define int long long 13 #define PII pair<int, int> 14 #define sf(x) scanf("%lld",&x) 15 #define ytz int _; sf(_); while(_--) 16 #define fory(i,a,b) for(int i = a; i <= b; ++i) 17 #define forl(i,a,b) for(int i = a; i >= b; --i) 18 #define debug(a) cout << #a << " = " << a <<endl; 19 const int N = 1e5 + 10; 20 struct node 21 { 22 int to, next; 23 } e[N << 1]; 24 int cnt, head[N]; 25 vector<PII> op; 26 map<pair<int, int>, int> ans; 27 int vis[N]; 28 int c[N]; 29 int n; 30 inline void init() 31 { 32 cnt = 0; 33 fory(i, 0, n) head[i] = -1, c[i] = vis[i] = 0; 34 ans.clear(); 35 op.clear(); 36 } 37 inline void add_edge(int u, int v) 38 { 39 e[++cnt].to = v; 40 e[cnt].next = head[u]; 41 head[u] = cnt; 42 c[v]++; 43 } 44 void dfs(int root, int num) 45 { 46 47 vis[root] = 1; 48 for(int i = head[root]; ~i; i = e[i].next) 49 { 50 int j = e[i].to; 51 if(!vis[j]) 52 { 53 ans[ {root, j}] = ans[ {j, root}] = num; 54 dfs(j, 5 - num); 55 } 56 } 57 } 58 void solve() 59 { 60 sf(n); 61 init(); 62 for(int i = 0; i < n - 1; ++i) 63 { 64 int x, y; 65 sf(x), sf(y); 66 add_edge(x, y), add_edge(y, x); 67 op.push_back({x, y}); 68 } 69 for(auto t : op) 70 { 71 if(c[t.first] > 2 || c[t.second] > 2) 72 { 73 puts("-1"); 74 return; 75 } 76 } 77 fory(i, 1, n) 78 { 79 if(c[i] == 1) 80 { 81 dfs(i, 3); 82 break; 83 } 84 } 85 for(auto t : op) 86 { 87 printf("%lld ", ans[ {t.first, t.second}]); 88 } 89 puts(""); 90 } 91 signed main() 92 { 93 ytz 94 { 95 solve(); 96 } 97 return 0; 98 }
这篇关于Not Assigning(1400)的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-04-17基于SpringWeb MultipartFile文件上传、下载功能
- 2024-04-14个人开发者,Spring Boot 项目如何部署
- 2024-04-14RAG应用开发实战02-相似性检索的关键 - Embedding
- 2024-04-14出海软件草根逆袭打法是什么?
- 2024-04-13鸿蒙原生应用再新丁!企查查 碧蓝航线 入局鸿蒙
- 2024-04-11RAG应用开发实战(01)-RAG应用框架和解析器
- 2024-04-10DevOps已死?2024年的DevOps将如何发展
- 2024-04-10码农必看:常见源代码混淆技术详解
- 2024-04-07以一当十丨TiDB 在东吴证券秀财 APP 的应用实践
- 2024-04-07月活超 1.1 亿,用户超 4 亿,你也在用的「知乎」是如何在超大规模 TiDB 集群上玩转多云多活的?来听听知乎代晓磊的答案!