結果
問題 | No.1647 Travel in Mitaru city 2 |
ユーザー | yunix91201367 |
提出日時 | 2021-08-13 23:14:36 |
言語 | C++14 (gcc 12.3.0 + boost 1.83.0) |
結果 |
WA
|
実行時間 | - |
コード長 | 3,724 bytes |
コンパイル時間 | 2,227 ms |
コンパイル使用メモリ | 188,852 KB |
実行使用メモリ | 21,956 KB |
最終ジャッジ日時 | 2024-04-14 20:24:39 |
合計ジャッジ時間 | 14,504 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge4 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2 ms
6,816 KB |
testcase_01 | AC | 2 ms
6,944 KB |
testcase_02 | AC | 2 ms
6,940 KB |
testcase_03 | AC | 2 ms
6,940 KB |
testcase_04 | AC | 4 ms
6,940 KB |
testcase_05 | AC | 2 ms
6,940 KB |
testcase_06 | AC | 2 ms
6,944 KB |
testcase_07 | AC | 7 ms
7,040 KB |
testcase_08 | WA | - |
testcase_09 | WA | - |
testcase_10 | AC | 188 ms
21,080 KB |
testcase_11 | AC | 106 ms
15,616 KB |
testcase_12 | WA | - |
testcase_13 | AC | 91 ms
14,620 KB |
testcase_14 | WA | - |
testcase_15 | WA | - |
testcase_16 | AC | 173 ms
20,268 KB |
testcase_17 | AC | 114 ms
15,872 KB |
testcase_18 | WA | - |
testcase_19 | AC | 133 ms
17,664 KB |
testcase_20 | WA | - |
testcase_21 | AC | 174 ms
19,840 KB |
testcase_22 | AC | 202 ms
21,796 KB |
testcase_23 | AC | 195 ms
21,696 KB |
testcase_24 | WA | - |
testcase_25 | WA | - |
testcase_26 | WA | - |
testcase_27 | AC | 206 ms
21,680 KB |
testcase_28 | AC | 210 ms
21,756 KB |
testcase_29 | AC | 208 ms
21,628 KB |
testcase_30 | AC | 166 ms
20,176 KB |
testcase_31 | AC | 207 ms
21,632 KB |
testcase_32 | WA | - |
testcase_33 | AC | 167 ms
19,972 KB |
testcase_34 | AC | 203 ms
21,760 KB |
testcase_35 | WA | - |
testcase_36 | AC | 208 ms
21,752 KB |
testcase_37 | AC | 205 ms
21,760 KB |
testcase_38 | WA | - |
testcase_39 | AC | 150 ms
19,200 KB |
testcase_40 | WA | - |
testcase_41 | WA | - |
testcase_42 | WA | - |
testcase_43 | AC | 2 ms
6,944 KB |
testcase_44 | AC | 5 ms
8,064 KB |
testcase_45 | AC | 89 ms
14,592 KB |
testcase_46 | AC | 123 ms
14,592 KB |
testcase_47 | AC | 92 ms
14,464 KB |
testcase_48 | WA | - |
testcase_49 | WA | - |
testcase_50 | AC | 88 ms
14,720 KB |
ソースコード
#include <bits/stdc++.h> #include <atcoder/math> using namespace std; using namespace atcoder; #define int long long using vec_int = vector<int>; using vec_ii = vector<vec_int>; using vec_iii = vector<vec_ii>; using vec_iiii = vector<vec_iii>; using P = pair<int,int>; using T = tuple<int,int,int>; using ll = long long; using ld = long double; #define rep(i, n) for(int i = 0; i < (int)(n); i++) void cout_line(vector<int> &a){ for(int i=0;i<a.size();i++){ if(i<a.size()-1){ cout<<a.at(i)<<" "; }else{ cout<<a.at(i)<<endl; } } } int charToInt(char c){ char zero_num = '0'; return (int)c - (int)zero_num; } signed main(){ int H, W, N; cin>>H>>W>>N; vec_int x(N), y(N); rep(i,N)cin>>x.at(i)>>y.at(i); vector<vec_int> x_city(H+1); vector<vec_int> y_city(W+1); rep(i, N){ x_city.at(x.at(i)).push_back(i); y_city.at(y.at(i)).push_back(i); } vec_int visited(N+1, -2); queue<T> que; for(int i=0;i<N;i++){ if(visited.at(i)==-2){ que.emplace(i, 0, -1); que.emplace(i, 1, -1); }else{ continue; } int flag = 0; int pos1, pos2; map<int,int> visited_map; while(!que.empty()){ int pos, direc, prev; tie(pos, direc, prev) = que.front(); que.pop(); //cout<<"pos:"<<pos<<" "<<direc<<endl; if(visited_map.count(pos)){ if(visited_map[pos]>=-1&&prev>=0){ pos1 = pos; pos2 = prev; flag = 1; break; } } visited_map[pos] = prev; if(direc==0){ for(auto next: x_city.at(x.at(pos))){ if(next==pos)continue; if(visited.at(next)>0)continue; que.emplace(next, 1, pos); } }else{ for(auto next: y_city.at(y.at(pos))){ if(next==pos)continue; if(visited.at(next)>0)continue; que.emplace(next, 0, pos); } } } if(flag==0){ for(auto temp:visited_map){ visited.at(temp.first) = 1; } continue; } vec_int route1, route2; while(pos1>=0){ route1.push_back(pos1); pos1 = visited_map[pos1]; } reverse(route1.begin(), route1.end()); while(pos2>=0){ route2.push_back(pos2); pos2 = visited_map[pos2]; } reverse(route2.begin(), route2.end()); int ind = 0; for(int i=0;i<route1.size()&&i<route2.size();i++){ if(route1.at(i)!=route2.at(i))break; ind = i+1; } vec_int ans; for(int i=ind;i<route1.size();i++){ ans.push_back(route1.at(i)+1); } reverse(ans.begin(), ans.end()); /* ans.push_back(route1.at(ind-1)+1); */ int pos0 = route1.at(ind-1); int poss1 = route1.at(ind); int poss2 = route2.at(ind); int flag1, flag2; if(x.at(poss1)==x.at(pos0)){ flag1 = 0; }else{ flag1 = 1; } if(x.at(poss2)==x.at(pos0)){ flag2 = 0; }else{ flag2 = 1; } if(flag1!=flag2){ ans.push_back(route1.at(ind-1)+1); } for(int i=ind;i<route2.size();i++){ ans.push_back(route2.at(i)+1); } cout<<ans.size()<<endl; cout_line(ans); return 0; } cout<<-1<<endl; return 0; }