This documentation is automatically generated by online-judge-tools/verification-helper
View the Project on GitHub ningenMe/compro-library
#define PROBLEM "https://yukicoder.me/problems/no/13" #include <vector> #include <iostream> #include <algorithm> #include <cassert> #include <set> #include <queue> #include <map> #include <stack> #include <array> using namespace std; #include "../../lib/40-graph/Graph.cpp" #include "../../lib/15-queue/RadixHeap.cpp" #include "../../lib/40-graph/MinimumUndirectedClosedCircuit.cpp" int main(){ cin.tie(0);ios::sync_with_stdio(false); int W,H; cin >> W >> H; Graph<int> g(H,W); vector<int> a(W),b(W); { for(int j=0;j <W;++j) cin >> a[j]; for(int j=0;j+1<W;++j) if(a[j]==a[j+1]) g.make_bidirectional_edge({0,j},{0,j+1},1); } for(int i=1;i<H;++i) { b=a; for(int j=0;j <W;++j) cin >> a[j]; for(int j=0;j <W;++j) if(b[j]==a[j]) g.make_bidirectional_edge({i,j},{i-1,j},1); for(int j=0;j+1<W;++j) if(a[j]==a[j+1]) g.make_bidirectional_edge({i,j},{i,j+1},1); } int inf = 12345678; MinimumUndirectedClosedCircuit<int> mucc(g,inf); int flg = 0; for(int i=0;i<H;++i) for(int j=0;j<W;++j) { int sz = mucc.solve(g.idx({i,j})); if(sz < inf) flg = 1; } cout << (flg?"possible":"impossible") << endl; return 0; }
#line 1 "test/graph/MinimumUndirectedClosedCircuit.test.cpp" #define PROBLEM "https://yukicoder.me/problems/no/13" #include <vector> #include <iostream> #include <algorithm> #include <cassert> #include <set> #include <queue> #include <map> #include <stack> #include <array> using namespace std; #line 1 "lib/40-graph/Graph.cpp" /* * @title Graph * @docs md/graph/Graph.md */ template<class T> class Graph{ private: const size_t N,H,W; public: vector<vector<pair<size_t,T>>> edges; Graph(const size_t N):H(-1),W(-1),N(N), edges(N) {} Graph(const size_t H, const size_t W):H(H),W(W),N(H*W), edges(H*W) {} inline void make_edge(size_t from, size_t to, T w) { edges[from].emplace_back(to,w); } //{from_y,from_x} -> {to_y,to_x} inline void make_edge(pair<size_t,size_t> from, pair<size_t,size_t> to, T w) { make_edge(from.first*W+from.second,to.first*W+to.second,w); } inline void make_bidirectional_edge(size_t from, size_t to, T w) { make_edge(from,to,w); make_edge(to,from,w); } inline void make_bidirectional_edge(pair<size_t,size_t> from, pair<size_t,size_t> to, T w) { make_edge(from.first*W+from.second,to.first*W+to.second,w); make_edge(to.first*W+to.second,from.first*W+from.second,w); } inline size_t size(){return N;} inline size_t idx(pair<size_t,size_t> yx){return yx.first*W+yx.second;} }; #line 1 "lib/15-queue/RadixHeap.cpp" /* * @title RadixHeap - 非負整数heap * @docs md/queue/RadixHeap.md */ template<class T, class Key = unsigned long long> class RadixHeap{ using TypeNode = pair<Key, T>; template<class InnerKey, class ZZ=InnerKey> class Inner{}; template<class InnerKey> class Inner<InnerKey, unsigned long long>{ array<vector<TypeNode>,65> vq; unsigned long long size_num; TypeNode last; inline int bit(unsigned long long a) { return a ? 64 - __builtin_clzll(a) : 0;} public: Inner(T mini) : size_num(0), last(make_pair(0, mini)) {} inline bool empty() { return size_num == 0; } inline size_t size(){ return size_num; } inline void push(TypeNode x){ ++size_num; vq[bit(x.first^last.first)].push_back(x);} inline void emplace(unsigned long long key,T val){ ++size_num; vq[bit(key^last.first)].emplace_back(key,val);} inline TypeNode pop() { if(vq[0].empty()) { int i = 1; while(vq[i].empty()) ++i; last = *min_element(vq[i].begin(),vq[i].end()); for(auto &p : vq[i]) vq[bit(p.first ^ last.first)].push_back(p); vq[i].clear(); } --size_num; auto res = vq[0].back(); vq[0].pop_back(); return res; } }; template<class InnerKey> class Inner<InnerKey, unsigned int>{ array<vector<TypeNode>,33> vq; unsigned int size_num; TypeNode last; inline int bit(unsigned int a) { return a ? 32 - __builtin_clz(a) : 0;} public: Inner(T mini) : size_num(0), last(make_pair(0, mini)) {} inline bool empty() { return size_num == 0; } inline size_t size(){ return size_num; } inline void push(TypeNode x){ ++size_num; vq[bit(x.first^last.first)].push_back(x);} inline void emplace(unsigned int key,T val){ ++size_num; vq[bit(key^last.first)].emplace_back(key,val);} inline TypeNode pop() { if(vq[0].empty()) { int i = 1; while(vq[i].empty()) ++i; last = *min_element(vq[i].begin(),vq[i].end()); for(auto &p : vq[i]) vq[bit(p.first ^ last.first)].push_back(p); vq[i].clear(); } --size_num; auto res = vq[0].back(); vq[0].pop_back(); return res; } }; Inner<Key,Key> inner; public: RadixHeap(T mini) : inner(mini) {} inline bool empty() { return inner.empty();} inline size_t size(){ return inner.size();} inline void push(TypeNode x){ inner.push(x);} inline void emplace(unsigned long long key,T val){ inner.emplace(key,val);} inline TypeNode pop() { return inner.pop(); } }; #line 1 "lib/40-graph/MinimumUndirectedClosedCircuit.cpp" /* * @title MinimumUndirectedClosedCircuit - 無向グラフの最小閉路検出 * @docs md/graph/MinimumUndirectedClosedCircuit.md */ template<class T> class MinimumUndirectedClosedCircuit { //Tは整数型のみ static_assert(std::is_integral<T>::value, "template parameter T must be integral type"); Graph<T> graph; vector<T> dist; vector<int> parent,label; size_t N; T inf; int last_l,last_r,root; private: void solve_impl() { RadixHeap<int, unsigned int> q(0); q.push({0,root}); dist[root] = 0; while (q.size()) { auto top = q.pop(); size_t curr = top.second; if(top.first > dist[curr]) continue; for(auto& edge:graph.edges[curr]){ size_t next = edge.first; T w = edge.second; if(parent[curr] == next) continue; if(dist[next] > dist[curr] + w) { dist[next] = dist[curr] + w; parent[next] = curr; label[next] = (curr==root?next:label[curr]); q.push({dist[next],next}); } } } } T solve_cycle() { T mini = inf; last_l=-1,last_r=-1; for(int l=0;l<N;++l) { if(l==root) continue; for(auto& edge:graph.edges[l]){ int r = edge.first; T w = edge.second; if(mini <= dist[l] + dist[r] + w) continue; if( (r==root && l!=label[l]) || (r!=root && label[l]!=label[r]) ) { mini = dist[l] + dist[r] + w; last_l = l; last_r = r; } } } return mini; } public: MinimumUndirectedClosedCircuit(Graph<T>& graph, T inf) : graph(graph),N(graph.size()),dist(graph.size()),parent(graph.size()),label(graph.size()),inf(inf) { } //rootを含む最小閉路の集合を返す O(NlogN) 閉路がないときは空集合 inline T solve(size_t rt){ root = rt; //初期化 for(int i = 0; i < N; ++i) dist[i] = inf, parent[i] = -1; solve_impl(); T mini=solve_cycle(); return mini; } //復元 vector<int> restore() { stack<int> s; queue<int> q; vector<int> res; if(last_l != -1 && last_r != -1){ for(int curr = last_l; curr != -1; curr = parent[curr]) s.push(curr); for(int curr = last_r; curr != root; curr = parent[curr]) q.push(curr); while(s.size()) res.push_back(s.top()) ,s.pop(); while(q.size()) res.push_back(q.front()),q.pop(); } return res; } }; #line 17 "test/graph/MinimumUndirectedClosedCircuit.test.cpp" int main(){ cin.tie(0);ios::sync_with_stdio(false); int W,H; cin >> W >> H; Graph<int> g(H,W); vector<int> a(W),b(W); { for(int j=0;j <W;++j) cin >> a[j]; for(int j=0;j+1<W;++j) if(a[j]==a[j+1]) g.make_bidirectional_edge({0,j},{0,j+1},1); } for(int i=1;i<H;++i) { b=a; for(int j=0;j <W;++j) cin >> a[j]; for(int j=0;j <W;++j) if(b[j]==a[j]) g.make_bidirectional_edge({i,j},{i-1,j},1); for(int j=0;j+1<W;++j) if(a[j]==a[j+1]) g.make_bidirectional_edge({i,j},{i,j+1},1); } int inf = 12345678; MinimumUndirectedClosedCircuit<int> mucc(g,inf); int flg = 0; for(int i=0;i<H;++i) for(int j=0;j<W;++j) { int sz = mucc.solve(g.idx({i,j})); if(sz < inf) flg = 1; } cout << (flg?"possible":"impossible") << endl; return 0; }