volochai

345D

Sep 27th, 2023
820
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 4.00 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.  
  5. #pragma GCC optimize("Ofast")
  6. #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
  7.  
  8. #define ll long long
  9. #define all(x) (x).begin(), (x).end()
  10. #define rall(x) (x).rbegin(), (x).rend()
  11. #define watch(x) cout << (#x) << " : " << x << '\n'
  12. #define boost ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  13.  
  14. using namespace std;
  15. using namespace __gnu_pbds;
  16.  
  17. const int N = 1e5 + 128;
  18. int cnt[N], len[N];
  19. vector <int> seg[N];
  20. int st[N][2];
  21. gp_hash_table <int, vector<pair<int, int>>> g;
  22. gp_hash_table <int, int> in, out;
  23. int n;
  24. unordered_set <int> vertices;
  25.  
  26. bool pathExist() {
  27.     int cnt0 = 0, cnt1 = 0;
  28.     bool ok = true;
  29.     for (auto& i : vertices)
  30.         if (in[i]-out[i] == 1)
  31.             cnt0++;
  32.         else if (out[i]-in[i] == 1)
  33.             cnt1++;
  34.         else
  35.             ok &= (in[i] == out[i]);
  36.  
  37.     return (ok && (cnt0 + cnt1 == 0 || (cnt0 == 1 && cnt1 == 1)));
  38. }
  39.  
  40. int findStart() {
  41.     for (auto& i : vertices)
  42.         if (out[i] - in[i] == 1)
  43.             return i;
  44.     return -1;
  45. }
  46.  
  47. int findEnd() {
  48.     for (auto& i : vertices)
  49.         if (in[i] - out[i] == 1)
  50.             return i;
  51.     return -1;
  52. }
  53.  
  54. vector <int> res;
  55.  
  56. void dfs(int v) {
  57.     while (!g[v].empty()) {
  58.         auto [nxt, id] = g[v].back(); g[v].pop_back();
  59.         dfs(nxt);
  60.         res.push_back(id);
  61.     }
  62. }
  63.  
  64. vector <int> getPath() {
  65.     int start = findStart(), finish = findEnd();
  66.     if (start != -1 && finish != -1)
  67.         g[finish].push_back(make_pair(start, n + 1));
  68.     dfs((start == -1 ? st[0][0] : start));
  69.  
  70.     int need = n + (start != -1 && finish != -1);
  71.     if ((int)res.size() != need)
  72.         return {};
  73.  
  74.     if (start != -1 && finish != -1) {
  75.         int pos = find(all(res), n + 1) - res.begin();
  76.         vector <int> total_res;
  77.  
  78.         for (int i = pos + 1; i < (int)res.size(); i++)
  79.             total_res.push_back(res[i]);
  80.         for (int i = 0; i < pos; i++)
  81.             total_res.push_back(res[i]);
  82.  
  83.         res = vector<int>(total_res.rbegin(), total_res.rend());
  84.     } else {
  85.         reverse(all(res));
  86.     }
  87.  
  88.     return res;
  89. }
  90.  
  91. void solve() {
  92.     cin >> n;
  93.     unordered_set <int> total;
  94.  
  95.     for (int i = 0; i < n; i++) {
  96.         cin >> cnt[i] >> len[i];
  97.         seg[i].resize(cnt[i]);
  98.         for (auto& x : seg[i])
  99.             cin >> x;
  100.         for (int j = 1; j < cnt[i]; j++)
  101.             total.insert(seg[i][j]-seg[i][j-1]);
  102.         st[i][0] = seg[i][0];
  103.         st[i][1] = len[i]-seg[i][cnt[i]-1];
  104.     }
  105.  
  106.     if ((int)total.size() > 1) {
  107.         cout << "No\n";
  108.         return;
  109.     }
  110.  
  111.     if (total.empty()) {
  112.         vector <int> first, last;
  113.         for (int i = 0; i < n; i++)
  114.             first.push_back(st[i][0]), last.push_back(st[i][1]);
  115.         sort(all(first)); sort(all(last));
  116.  
  117.         for (int a : {0, 1})
  118.             for (int b : {n - 1, n - 2})
  119.                 if (0 <= a && a < (int)first.size() && 0 <= b && b < (int)last.size())
  120.                     total.insert(first[a] + last[b]);
  121.  
  122.         for (int a : {n - 1, n - 2})
  123.             for (int b : {0, 1})
  124.                 if (0 <= a && a < (int)first.size() && 0 <= b && b < (int)last.size())
  125.                     total.insert(first[a] + last[b]);
  126.     }
  127.  
  128.     for (auto& k : total) {
  129.         g.clear(); in.clear(); out.clear(); vertices.clear();
  130.         for (int i = 0; i < n; i++) {
  131.             int u = st[i][0];
  132.             int v = k - st[i][1];
  133.  
  134.             g[u].push_back(make_pair(v, i + 1));
  135.             in[v]++; out[u]++;
  136.  
  137.             vertices.insert(v); vertices.insert(u);
  138.         }
  139.  
  140.         if (!pathExist())
  141.             continue;
  142.  
  143.         vector <int> ans = getPath();
  144.  
  145.         if (ans.empty())
  146.             continue;
  147.  
  148.         cout << "Yes\n";
  149.         for (auto c : ans)
  150.             cout << c << ' ';
  151.         cout << '\n';
  152.         return;
  153.     }
  154.  
  155.     cout << "No\n";
  156.  
  157. }
  158.  
  159. main() {
  160.     boost;
  161.     solve();
  162.     return 0;
  163. }
  164.  
Advertisement
Add Comment
Please, Sign In to add comment