Advertisement
Guest User

Untitled

a guest
Jun 25th, 2018
59
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 2.83 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2. //#include <ext/pb_ds/assoc_container.hpp>
  3. //#include <ext/pb_ds/tree_policy.hpp>
  4. //#include <ext/pb_ds/detail/standard_policies.hpp>
  5.  
  6. using namespace std;
  7. //using namespace __gnu_pbds;
  8.  
  9. #define F first
  10. #define S second
  11. #define pb push_back
  12. //#define mt make_tuple
  13. //#define mp make_pair
  14.  
  15. typedef long long ll;
  16.  
  17. //typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;
  18.  
  19. const int rx[4] = {-1, 1, 0, 0};
  20. const int ry[4] = {0, 0, 1, -1};
  21.  
  22. const int N = 100100;
  23.  
  24. unordered_map<int, int> mp;
  25. vector<pair<int, int>> e;
  26. vector<int> g[N];
  27. int p[N];
  28. int n;
  29. vector<pair<int, int>> ans;
  30.  
  31. void dfs(int v, int pr = -1){
  32. while (p[v] < g[v].size()){
  33. int i = p[v];
  34. if (mp.count(g[v][i]) == 1){
  35. p[v]++;
  36. continue;
  37. }
  38. mp[g[v][i]] = 1;
  39. int to = (e[g[v][i]].F == v ? e[g[v][i]].S : e[g[v][i]].F);
  40. p[v]++;
  41. dfs(to, v);
  42. }
  43. if (pr != -1){
  44. ans.pb({pr, v});
  45. }
  46. }
  47.  
  48. #define FILE "euler"
  49. int main() {
  50. ios_base::sync_with_stdio(0);
  51. #ifdef LOCAL
  52. freopen("input.txt", "r", stdin);
  53. // freopen("output.txt", "w", stdout);
  54. #else
  55. freopen(FILE".in", "r", stdin);
  56. freopen(FILE".out", "w", stdout);
  57. #endif // LOCAL
  58. mp.reserve(300000);
  59. mp.max_load_factor(0.25);
  60. scanf("%d", &n);
  61. for (int i = 0; i < n; i++){
  62. int k;
  63. scanf("%d", &k);
  64. while (k--){
  65. int x;
  66. scanf("%d", &x);
  67. if (x - 1 < i) continue;
  68. e.pb({i, x - 1});
  69. g[i].pb(e.size() - 1);
  70. g[x - 1].pb(e.size() - 1);
  71. }
  72. p[i] = 0;
  73. }
  74. vector<int> _ch;
  75. for (int i = 0; i < n; i++){
  76. if (g[i].size() % 2 == 1){
  77. _ch.pb(i);
  78. }
  79. }
  80. if (_ch.size() != 0 && _ch.size() != 2){
  81. printf("-1\n");
  82. return 0;
  83. }
  84. bool rev = false;
  85. int start = 0;
  86. if (_ch.size() == 2){
  87. rev = true;
  88. int a = _ch[_ch.size() - 1];
  89. int b = _ch[_ch.size() - 2];
  90. start = a;
  91. vector<bool> bad(g[a].size(), false);
  92. int p = 0;
  93. for (int x : g[a]){
  94. if (e[x].F == b || e[x].S == b){
  95. bad[p] = true;
  96. }
  97. p++;
  98. }
  99. vector<int> cur = g[a];
  100. g[a].clear();
  101. for (int i = 0; i < cur.size(); i++){
  102. if (!bad[i]){
  103. g[a].pb(cur[i]);
  104. }
  105. }
  106. for (int i = 0; i < cur.size(); i++){
  107. if (bad[i]){
  108. g[a].pb(cur[i]);
  109. }
  110. }
  111.  
  112. // e.pb({a, b});
  113. // g[a].pb(e.size() - 1);
  114. // swap(g[a][0], g[a].back());
  115. // g[b].pb(e.size() - 1);
  116. // swap(g[b][0], g[b].back());
  117. }
  118. dfs(start);
  119. reverse(ans.begin(), ans.end());
  120. // if (rev) {
  121. // ans.pop_back();
  122. // }
  123. printf("%d\n", ans.size());
  124. for (auto to : ans) printf("%d ", to.F + 1);
  125. printf("%d ", ans.back().S + 1);
  126.  
  127.  
  128. //#ifdef LOCAL
  129. // cerr << "TIME = " << fixed << 1.0 * clock() / CLOCKS_PER_SEC << endl;
  130. //#endif // LOCAL
  131. return 0;
  132. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement