結果
問題 | No.1373 Directed Operations |
ユーザー |
![]() |
提出日時 | 2021-02-05 21:46:56 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 62 ms / 2,000 ms |
コード長 | 1,885 bytes |
コンパイル時間 | 2,328 ms |
コンパイル使用メモリ | 211,596 KB |
最終ジャッジ日時 | 2025-01-18 12:11:29 |
ジャッジサーバーID (参考情報) |
judge3 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 19 |
ソースコード
#include <bits/stdc++.h> using namespace std; template <class A, class B> bool cmin(A& a, B b) { return a > b && (a = b, true); } template <class A, class B> bool cmax(A& a, B b) { return a < b && (a = b, true); } class UnionFind { private: int N; vector<int> PS; public: UnionFind() : N(0) {} UnionFind(int n) : N(n), PS(n, -1) {} bool unite(int a, int b) { int x = root(a), y = root(b); if (x == y) return false; if (-PS.at(x) < -PS.at(y)) swap(x, y); PS.at(x) += PS.at(y); PS.at(y) = x; return true; } bool same(int a, int b) { return root(a) == root(b); } int root(int a) { if (PS.at(a) < 0) return a; return PS.at(a) = root(PS.at(a)); } int size(int a) { return -PS.at(root(a)); } vector<vector<int>> groups() { vector<int> B(N), S(N); for (int i = 0; i < N; i++) { B.at(i) = root(i); S.at(B.at(i))++; } vector<vector<int>> ret(N); for (int i = 0; i < N; i++) { ret.at(i).reserve(S.at(i)); } for (int i = 0; i < N; i++) { ret.at(B.at(i)).push_back(i); } auto f = [&](const vector<int> &v) { return v.empty(); }; ret.erase(remove_if(ret.begin(), ret.end(), f), ret.end()); return ret; } }; signed main() { cin.tie(nullptr)->sync_with_stdio(false); int N; cin >> N; vector<tuple<int, int, int>> A(N - 1); for (int i = 0; i < N - 1; i++) { int a; cin >> a; A.at(i) = {a, i, 0}; } sort(A.begin(), A.end()); UnionFind UF(N); for (int i = N - 2; i >= 0; i--) { auto&& [a, b, c] = A.at(i); if (i + 1 - a < 0) return cout << "NO" << '\n', 0; UF.unite(i + 1, i + 1 - a); c = i - a; } if (UF.size(0) != N) return cout << "NO" << '\n', 0; cout << "YES" << '\n'; sort(A.begin(), A.end(), [](auto a, auto b) { return get<1>(a) < get<1>(b); }); for (const auto& [a, b, c] : A) cout << c + 2 << '\n'; }