結果
問題 | No.1647 Travel in Mitaru city 2 |
ユーザー |
![]() |
提出日時 | 2021-08-13 22:37:51 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 179 ms / 2,500 ms |
コード長 | 2,403 bytes |
コンパイル時間 | 4,010 ms |
コンパイル使用メモリ | 185,288 KB |
最終ジャッジ日時 | 2025-01-23 20:20:03 |
ジャッジサーバーID (参考情報) |
judge3 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 48 |
ソースコード
#include <cstdio>#include <cstring>#include <iostream>#include <string>#include <cmath>#include <bitset>#include <vector>#include <map>#include <set>#include <queue>#include <deque>#include <algorithm>#include <complex>#include <unordered_map>#include <unordered_set>#include <random>#include <cassert>#include <fstream>#include <utility>#include <functional>#include <time.h>#include <stack>#include <array>#include <list>#include <atcoder/all>#define popcount __builtin_popcountusing namespace std;using namespace atcoder;typedef long long ll;typedef pair<int, int> P;struct unionfind{vector<int> par, sz;unionfind() {}unionfind(int n):par(n), sz(n, 1){for(int i=0; i<n; i++) par[i]=i;}int find(int x){if(par[x]==x) return x;return par[x]=find(par[x]);}void unite(int x, int y){x=find(x); y=find(y);if(x==y) return;if(sz[x]>sz[y]) swap(x, y);par[x]=y;sz[y]+=sz[x];}bool same(int x, int y){return find(x)==find(y);}int size(int x){return sz[find(x)];}};int main(){int h, w, n;cin>>h>>w>>n;int x[100010], y[100010];int n1=100000;vector<P> g[200020];unionfind uf(2*n1);vector<int> ans;int par[200020];auto dfs=[&](auto dfs, int x, int p)->void{for(auto q:g[x]){if(q.first==p){par[x]=q.second;}else{dfs(dfs, q.first, x);}}};for(int i=0; i<n; i++){cin>>x[i]>>y[i];x[i]--; y[i]--;if(uf.same(x[i], y[i]+n1)){dfs(dfs, y[i]+n1, -1);int v=x[i];while(v!=y[i]+n1){ans.push_back(par[v]);if(v<n1){v=y[par[v]]+n1;}else{v=x[par[v]];}}ans.push_back(i);reverse(ans.begin(), ans.end());cout<<ans.size()<<endl;for(int i=0; i<ans.size(); i++){cout<<ans[i]+1;if(i<(int)ans.size()-1) cout<<" ";}cout<<endl;return 0;}uf.unite(x[i], y[i]+n1);g[x[i]].push_back({y[i]+n1,i});g[y[i]+n1].push_back({x[i],i});}cout<<-1<<endl;return 0;}