Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- #include <ext/pb_ds/assoc_container.hpp>
- #include <ext/pb_ds/tree_policy.hpp>
- #pragma GCC optimize("Ofast")
- #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
- #define ll long long
- #define all(x) (x).begin(), (x).end()
- #define rall(x) (x).rbegin(), (x).rend()
- #define watch(x) cout << (#x) << " : " << x << '\n'
- #define boost ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
- using namespace std;
- using namespace __gnu_pbds;
- const int N = 1e5 + 128;
- int cnt[N], len[N];
- vector <int> seg[N];
- int st[N][2];
- gp_hash_table <int, vector<pair<int, int>>> g;
- gp_hash_table <int, int> in, out;
- int n;
- unordered_set <int> vertices;
- bool pathExist() {
- int cnt0 = 0, cnt1 = 0;
- bool ok = true;
- for (auto& i : vertices)
- if (in[i]-out[i] == 1)
- cnt0++;
- else if (out[i]-in[i] == 1)
- cnt1++;
- else
- ok &= (in[i] == out[i]);
- return (ok && (cnt0 + cnt1 == 0 || (cnt0 == 1 && cnt1 == 1)));
- }
- int findStart() {
- for (auto& i : vertices)
- if (out[i] - in[i] == 1)
- return i;
- return -1;
- }
- int findEnd() {
- for (auto& i : vertices)
- if (in[i] - out[i] == 1)
- return i;
- return -1;
- }
- vector <int> res;
- void dfs(int v) {
- while (!g[v].empty()) {
- auto [nxt, id] = g[v].back(); g[v].pop_back();
- dfs(nxt);
- res.push_back(id);
- }
- }
- vector <int> getPath() {
- int start = findStart(), finish = findEnd();
- if (start != -1 && finish != -1)
- g[finish].push_back(make_pair(start, n + 1));
- dfs((start == -1 ? st[0][0] : start));
- int need = n + (start != -1 && finish != -1);
- if ((int)res.size() != need)
- return {};
- if (start != -1 && finish != -1) {
- int pos = find(all(res), n + 1) - res.begin();
- vector <int> total_res;
- for (int i = pos + 1; i < (int)res.size(); i++)
- total_res.push_back(res[i]);
- for (int i = 0; i < pos; i++)
- total_res.push_back(res[i]);
- res = vector<int>(total_res.rbegin(), total_res.rend());
- } else {
- reverse(all(res));
- }
- return res;
- }
- void solve() {
- cin >> n;
- unordered_set <int> total;
- for (int i = 0; i < n; i++) {
- cin >> cnt[i] >> len[i];
- seg[i].resize(cnt[i]);
- for (auto& x : seg[i])
- cin >> x;
- for (int j = 1; j < cnt[i]; j++)
- total.insert(seg[i][j]-seg[i][j-1]);
- st[i][0] = seg[i][0];
- st[i][1] = len[i]-seg[i][cnt[i]-1];
- }
- if ((int)total.size() > 1) {
- cout << "No\n";
- return;
- }
- if (total.empty()) {
- vector <int> first, last;
- for (int i = 0; i < n; i++)
- first.push_back(st[i][0]), last.push_back(st[i][1]);
- sort(all(first)); sort(all(last));
- for (int a : {0, 1})
- for (int b : {n - 1, n - 2})
- if (0 <= a && a < (int)first.size() && 0 <= b && b < (int)last.size())
- total.insert(first[a] + last[b]);
- for (int a : {n - 1, n - 2})
- for (int b : {0, 1})
- if (0 <= a && a < (int)first.size() && 0 <= b && b < (int)last.size())
- total.insert(first[a] + last[b]);
- }
- for (auto& k : total) {
- g.clear(); in.clear(); out.clear(); vertices.clear();
- for (int i = 0; i < n; i++) {
- int u = st[i][0];
- int v = k - st[i][1];
- g[u].push_back(make_pair(v, i + 1));
- in[v]++; out[u]++;
- vertices.insert(v); vertices.insert(u);
- }
- if (!pathExist())
- continue;
- vector <int> ans = getPath();
- if (ans.empty())
- continue;
- cout << "Yes\n";
- for (auto c : ans)
- cout << c << ' ';
- cout << '\n';
- return;
- }
- cout << "No\n";
- }
- main() {
- boost;
- solve();
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment