結果
問題 | No.2178 Payable Magic Items |
ユーザー |
![]() |
提出日時 | 2023-01-06 23:11:19 |
言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 227 ms / 4,000 ms |
コード長 | 5,800 bytes |
コンパイル時間 | 3,791 ms |
コンパイル使用メモリ | 261,664 KB |
実行使用メモリ | 46,888 KB |
最終ジャッジ日時 | 2024-12-14 18:05:20 |
合計ジャッジ時間 | 7,118 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 23 |
ソースコード
#include <bits/stdc++.h>using namespace std;#define rep(i,n) for(ll i = 0LL; i < (ll)n; i++)#define FOR(n) for(ll i = 0LL; i < (ll)n; i++)#define repi(i,a,b) for(ll i = (ll)a; i < (ll)b; i++)#define all(x) x.begin(),x.end()//#define mp make_pair#define vi vector<ll>#define vvi vector<vi>#define vll vector<ll>#define vvll vector<vll>#define vs vector<string>#define vvs vector<vs>#define vc vector<char>#define vvc vector<vc>#define pii pair<ll,ll>#define pllll pair<ll,ll>#define vpii vector<pair<ll,ll>>#define vpllll vector<pair<ll,ll>>#define vpis vector<pair<ll,string>>#define vplls vector<pair<ll, string>>#define vpsi vector<pair<string, ll>>#define vpsll vector<pair<string, ll>>template<typename T>void chmax(T &a, const T &b) {a = (a > b? a : b);}template<typename T>void chmin(T &a, const T &b) {a = (a < b? a : b);}using ll = long long;using ld = long double;using ull = unsigned long long;const ll INF = numeric_limits<long long>::max() / 2;const ld pi = acos(-1);const ll mod = 998244353;int dx[] = {-1, 0LL, 1, 0LL, -1, 1, -1, 1};int dy[] = {0LL, -1, 0LL, 1, -1, -1, 1, 1};#define int long longstruct UnionFind {vector<int> r;UnionFind(int n) {r = vector<int>(n, -1);}int root(int x) {if(r[x] < 0) return x;return r[x] = root(r[x]);}bool unite(int x, int y) {x = root(x);y = root(y);if(x == y) return false;if(r[x] > r[y]) swap(x, y);r[x] += r[y];r[y] = x;return true;}bool issame(int x, int y) {return root(x) == root(y);}int size(int x) {return -r[root(x)];}// int number_of_set() {// set<int> st;// for(int i = 0; i < (int)r.size(); i++) st.insert(root(i));// return st.size();// }// only vertices: not including leader pos// vector<vector<int>> decompose() {// vector<pair<int, int>> p;// for(int i = 0; i < (int)r.size(); i++) p.emplace_back(root(i), i);// sort(all(p));// //first:root, second:vertices// vector<vector<int>> ret;// int pre = -1;// for(pair<int, int> e : p) {// if(pre != e.first) {// ret.push_back(vector<int>{e.second});// }else {// ret.back().push_back(e.second);// }// pre = e.first;// }// return ret;// }//leader and groups vertex// vector<pair<int, vector<int>>> decompose() {// vector<pair<int, int>> p;// for(int i = 0; i < (int)r.size(); i++) p.emplace_back(root(i), i);// sort(all(p));// //first:root, second:vertices// vector<pair<int, vector<int>>> ret;// int pre = -1;// for(pair<int, int> e : p) {// if(pre != e.first) {// ret.push_back(make_pair(e.first, vector<int>{e.second}));// }else {// ret.back().second.push_back(e.second);// }// pre = e.first;// }// return ret;// }// vector<int> roots(vector<int> x) {// vector<int> ret((int)x.size());// for(int i = 0; i < (int)x.size(); i++) ret[i] = root(i);// return ret;// }// bool unite(pair<int, int> p) {// return unite(p.first, p.second);// }// vector<bool> unite(vector<pair<int, int>> p) {// vector<bool> ret((int)p.size());// for(int i = 0; i < (int)p.size(); i++) {// ret[i] = unite(p[i]);// }// return ret;// }// vector<bool> unite(vector<int> x, vector<int> y) {// assert(x.size() == y.size());// vector<bool> ret((int)x.size());// for(int i = 0; i < (int)x.size(); i++) {// ret[i] = unite(x[i], y[i]);// }// return ret;// }// bool issame(pair<int, int> p) {// return issame(p.first, p.second);// }};int to_ten(string s) {int ret = 0;int mul = 1;for(int i = s.size()-1; i >= 0; i--) {ret += mul * (s[i] - '0');mul *= 5;}return ret;}void solve() {int n, k;cin >> n >> k;vector<int> s(n);FOR(n) {string t;cin >> t;s[i] = to_ten(t);}int sz = 1;rep(i, k) sz *= 5;sz++;vvi g(sz);auto dfs = [&](string now, int id, auto self) -> void {if(id == k) {string v = now;rep(j, id) {if(v[j] != '0') {--v[j];g[to_ten(now)].push_back(to_ten(v));++v[j];}}}else {rep(i, 5) {now[id] = (char)(i + '0');self(now, id+1, self);}}};dfs(string(k, '@'), 0, dfs);vector<int> vis(sz, -1);auto bfs = [&](int st) -> void {vis[st] = 1;queue<int> que;que.push(st);while(que.size()) {int v = que.front();que.pop();for(auto e : g[v]) {if(vis[e] == -1) {vis[e] = 0;que.push(e);}else if(vis[e] == 1) {vis[e] = 0;}}}};sort(all(s));for(auto e : s) {if(vis[e] == -1) {bfs(e);}}cout << n - (int)count(all(vis), 1) << endl;// for(auto e : vis) {// cout << e << " ";// } cout << "\n";}//euler tourの点更新、辺更新の追加signed main() {cin.tie(nullptr);ios::sync_with_stdio(false);solve();return 0LL;}