結果
問題 | No.1370 置換門松列 |
ユーザー |
|
提出日時 | 2021-01-29 22:28:31 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 71 ms / 2,000 ms |
コード長 | 3,122 bytes |
コンパイル時間 | 2,440 ms |
コンパイル使用メモリ | 206,248 KB |
最終ジャッジ日時 | 2025-01-18 09:27:57 |
ジャッジサーバーID (参考情報) |
judge3 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 5 |
other | AC * 25 |
ソースコード
#include <bits/stdc++.h> using namespace std; #define rep(i, n) for(int i = 0; i < n; i++) #define rep2(i, x, n) for(int i = x; i <= n; i++) #define rep3(i, x, n) for(int i = x; i >= n; i--) #define each(e, v) for(auto &e: v) #define pb push_back #define eb emplace_back #define all(x) x.begin(), x.end() #define rall(x) x.rbegin(), x.rend() #define sz(x) (int)x.size() using ll = long long; using pii = pair<int, int>; using pil = pair<int, ll>; using pli = pair<ll, int>; using pll = pair<ll, ll>; const int MOD = 1000000007; //const int MOD = 998244353; const int inf = (1<<30)-1; const ll INF = (1LL<<60)-1; template<typename T> bool chmax(T &x, const T &y) {return (x < y)? (x = y, true) : false;}; template<typename T> bool chmin(T &x, const T &y) {return (x > y)? (x = y, true) : false;}; struct io_setup{ io_setup(){ ios_base::sync_with_stdio(false); cin.tie(NULL); cout << fixed << setprecision(15); } } io_setup; struct Graph{ vector<vector<int>> es; const int n; Graph(int n) : n(n){ es.resize(n); } void add_edge(int from, int to, bool directed = true){ es[from].pb(to); if(!directed) es[to].pb(from); } }; struct Strongly_Connected_Components{ vector<vector<int>> es, rs; vector<int> vs, comp; vector<bool> used; const int n; Strongly_Connected_Components(int n) : n(n){ es.resize(n), rs.resize(n); vs.resize(n), comp.resize(n), used.resize(n); } void add_edge(int from, int to, bool directed = false){ es[from].pb(to), rs[to].pb(from); if(!directed) es[to].pb(from), rs[from].pb(to); } void topological_sort(int now){ used[now] = true; each(e, es[now]) if(!used[e]) topological_sort(e); vs.pb(now); } void track_back(int now, int cnt){ used[now] = true, comp[now] = cnt; each(e, rs[now]) if(!used[e]) track_back(e, cnt); } Graph decompose(){ fill(all(used), false); rep(i, n) if(!used[i]) topological_sort(i); fill(all(used), false), reverse(all(vs)); int cnt = 0; each(e, vs) if(!used[e]) track_back(e, cnt++); Graph G(cnt); rep(i, n){ each(e, es[i]){ int u = comp[i], v = comp[e]; if(u != v) G.add_edge(u, v, true); } } return G; } int operator [] (int k) const {return comp[k];} }; int main(){ int N, M; cin >> N >> M; vector<int> a(N); rep(i, N) {cin >> a[i]; a[i]--;} Strongly_Connected_Components G(M); rep2(i, 1, N-2){ if(a[i-1] == a[i] || a[i] == a[i+1] || a[i-1] == a[i+1]){ cout << "No\n"; return 0; } if(i&1){ G.add_edge(a[i-1], a[i], true), G.add_edge(a[i+1], a[i], true); } else{ G.add_edge(a[i], a[i-1], true), G.add_edge(a[i], a[i+1], true); } } int m = G.decompose().n; if(m != M){ cout << "No\n"; return 0; } cout << "Yes\n"; rep(i, M) cout << G[i]+1 << ' '; cout << '\n'; }