結果
| 問題 |
No.1647 Travel in Mitaru city 2
|
| コンテスト | |
| ユーザー |
 むかで
|
| 提出日時 | 2021-08-13 23:20:43 |
| 言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
WA
|
| 実行時間 | - |
| コード長 | 6,020 bytes |
| コンパイル時間 | 2,621 ms |
| コンパイル使用メモリ | 214,964 KB |
| 最終ジャッジ日時 | 2025-01-23 21:20:20 |
|
ジャッジサーバーID （参考情報） |
judge4 / judge1 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 1 WA * 2 |
| other | AC * 2 WA * 46 |
ソースコード
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define FOR(i,n,m) for(int i=(int)(n); i<=(int)(m); i++)
#define RFOR(i,n,m) for(int i=(int)(n); i>=(int)(m); i--)
#define ITR(x,c) for(__typeof(c.begin()) x=c.begin();x!=c.end();x++)
#define RITR(x,c) for(__typeof(c.rbegin()) x=c.rbegin();x!=c.rend();x++)
#define setp(n) fixed << setprecision(n)
template<class T> bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T> bool chmin(T &a, const T &b) { if (a>b) { a=b; return 1; } return 0; }
#define ll long long
#define vll vector<ll>
#define vi vector<int>
#define pll pair<ll,ll>
#define pi pair<int,int>
#define all(a) (a.begin()),(a.end())
#define rall(a) (a.rbegin()),(a.rend())
#define fi first
#define se second
#define pb push_back
#define ins insert
#define debug(a) cerr<<(a)<<endl
#define dbrep(a,n) rep(_i,n) cerr<<(a[_i])<<" "; cerr<<endl
#define dbrep2(a,n,m) rep(_i,n){rep(_j,m) cerr<<(a[_i][_j])<<" "; cerr<<endl;}
using namespace std;
template<class A, class B>
ostream &operator<<(ostream &os, const pair<A,B> &p){return os<<"("<<p.fi<<","<<p.se<<")";}
template<class A, class B>
istream &operator>>(istream &is, pair<A,B> &p){return is>>p.fi>>p.se;}
template<class T>
vector<T> make_vec(size_t a){
return vector<T>(a);
}
template<class T, class... Ts>
auto make_vec(size_t a, Ts... ts){
return vector<decltype(make_vec<T>(ts...))>(a, make_vec<T>(ts...));
}
//-------------------------------------------------
//--Graph Template
//-------------------------------------------------
template<class E>
struct Graph
{
vector<vector<E> > adj;
Graph(int N):adj(N){}
virtual void add_edge(int v, E e){adj[v].push_back(e);}
vector<E>& operator[](int v){return adj[v];}
inline int size(){return adj.size();}
};
namespace graph {
struct SimpleEdge {
int to;
SimpleEdge(int to):to(to){}
};
}
struct UWGraph : public Graph<graph::SimpleEdge>
{
UWGraph(int N):Graph(N){}
void add_edge(int v, int e){adj[v].push_back({e});}
};
//-------------------------------------------------
//--Get Cycle Any
//-------------------------------------------------
namespace Cycle
{
stack<int> st;
vector<bool> seen,finished;
int pos;
template<class E>
void dfs(int v, int p, Graph<E> &G, bool dir=true){
st.push(v);
seen[v] = true;
for(auto &e:G[v]){
if (!dir && e.to==p) continue;
if (finished[e.to]) continue;
if (seen[e.to] && !finished[e.to]){
pos = e.to;
return;
}
dfs(e.to,v,G,dir);
if (pos!=-1) return;
}
finished[v] = true;
st.pop();
}
void init(int V){
pos = -1; st=stack<int>();
seen.resize(V,false);
finished.resize(V,false);
}
vector<int> restore(){
vector<int> ret;
if (pos==-1) return ret;
while(!st.empty()){
int u = st.top(); st.pop();
ret.push_back(u);
if (u==pos) break;
}
reverse(ret.begin(),ret.end());
return ret;
}
template<class E>
vector<int> get(Graph<E> &G, bool dir=true){
int V = G.size();
init(V);
for(int i=0;i<V;i++)if(!seen[i]){
dfs(i,-1,G,dir);
if (pos!=-1) break;
}
return restore();
}
template<class E>
vector<int> get(int v, Graph<E> &G, bool dir=true){
int V = G.size();
init(V);
dfs(v,-1,G,dir);
return restore();
}
template<class E>
vector<int> minimize(vector<int> &cycle, Graph<E> &G, bool dir=true){
vector<int> ret;
int L = cycle.size();
if (L==0) return ret;
unordered_map<int,int> Mp;
for(int j=0;j<L;j++) Mp[cycle[j]]=j;
int i=0;
while(i<L){
ret.push_back(cycle[i]);
int ni=i;
for(auto &e:G[cycle[i]]){
if (!dir && i==0 && e.to==cycle[L-1]) continue;
if (!dir && ret.size()<3 && e.to==cycle[0]) continue;
if (e.to==cycle[0]){
ni=L;
break;
}else{
chmax(ni,Mp[e.to]);
}
}
i=ni;
}
return ret;
}
}
//-------------------------------------------------
int main(void)
{
cin.tie(0);
ios::sync_with_stdio(false);
int H,W,N; cin>>H>>W>>N;
vector<vi> row(H), col(W);
rep(i,N){
int y,x; cin>>y>>x; y--; x--;
row[y].pb(i);
col[x].pb(i);
}
UWGraph G(4*N);
rep(i,H){
auto &vec = row[i];
int sz = vec.size();
rep(j,sz-1){
int from = vec[j];
int to = vec[j+1];
G.add_edge(from,to);
}
rep(j,sz-1){
int from = vec[j+1] + N;
int to = vec[j] + N;
G.add_edge(from,to);
}
rep(j,sz-1){
int from = vec[j] + 2*N;
int to = vec[j+1];
G.add_edge(from,to);
from = vec[j] + 3*N;
G.add_edge(from,to);
}
rep(j,sz-1){
int from = vec[j+1] + 2*N;
int to = vec[j] + N;
G.add_edge(from,to);
from = vec[j+1] + 3*N;
G.add_edge(from,to);
}
}
rep(i,W){
auto &vec = col[i];
int sz = vec.size();
rep(j,sz-1){
int from = vec[j] + 2*N;
int to = vec[j+1] + 2*N;
G.add_edge(from,to);
}
rep(j,sz-1){
int from = vec[j+1] + 3*N;
int to = vec[j] + 3*N;
G.add_edge(from,to);
}
rep(j,sz-1){
int from = vec[j];
int to = vec[j+1] + 2*N;
G.add_edge(from,to);
from = vec[j] + N;
G.add_edge(from,to);
}
rep(j,sz-1){
int from = vec[j+1];
int to = vec[j] + 3*N;
G.add_edge(from,to);
from = vec[j+1] + N;
G.add_edge(from,to);
}
}
auto cycle = Cycle::get(G);
if (cycle.empty()){
cout<<"-1\n";
}else{
int sz = cycle.size();
vi ans;
rep(i,sz){
if (i < sz-1){
int v1 = cycle[i]/N;
int v2 = cycle[i+1]/N;
if (v1 == v2) continue;
}
ans.pb(cycle[i]%N+1);
}
int V = ans.size();
rep(i,sz) cout<<ans[i]<<" \n"[i==V-1];
}
return 0;
}