제출 #674073

#제출 시각아이디문제언어결과실행 시간메모리
674073US3RN4M3수천개의 섬 (IOI22_islands)C++17
컴파일 에러
0 ms0 KiB
#include"islands.h" #include<vector> #include<algorithm> #include<iostream> using namespace std; using ll = long long; const int mx = 200005; bool is_cycle[mx]; int N; vector<pair<int, int>> graph[mx]; vector<pair<int, int>> bck[mx]; vector<vector<int>> groups; int group_id[mx]; bool vis[mx]; vector<int> topo; vector<int> ans; int cur_group_id; pair<int, int> par[mx]; void dfs(int cur) { vis[cur] = true; for(auto [nxt, id] : graph[cur]) if(!vis[nxt]) { dfs(nxt); } topo.push_back(cur); } void dfs2(int cur) { vis[cur] = true; for(auto [prv, id] : bck[cur]) if(!vis[prv]) { dfs2(prv); } group_id[cur] = cur_group_id; groups.back().push_back(cur); } pair<int, int> cycle_next[mx]; bool test_cycle(int bit) { ans.clear(); vector<int> tour1, tour2, cycle1, cycle2; for(int _ = 0; _ < 2; _++) { swap(tour1, tour2); swap(cycle1, cycle2); for(int i = 0; i < N; i++) vis[i] = false; vector<int> q; for(auto [nxt, id] : graph[0]) { if(_ == 0) { if((id >> bit) & 1) { if(vis[nxt]) continue; vis[nxt] = true; q.push_back(nxt); par[nxt] = {0, id}; } } else { if(!((id >> bit) & 1)) { if(vis[nxt]) continue; vis[nxt] = true; q.push_back(nxt); par[nxt] = {0, id}; } } } int qidx = 0; while(qidx < q.size()) { int cur = q[qidx++]; if(is_cycle[cur]) { int tmp = cur; while(tmp != 0) { tour1.push_back(par[tmp].second); tmp = par[tmp].first; } reverse(tour1.begin(), tour1.end()); tmp = cur; do { cycle1.push_back(cycle_next[tmp].second); tmp = cycle_next[tmp].first; } while(tmp != cur); break; } for(auto [nxt, id] : graph[cur]) { if(vis[nxt]) continue; par[nxt] = {cur, id}; vis[nxt] = true; q.push_back(nxt); } } } if(cycle1.size() == 0) return false; if(cycle2.size() == 0) return false; vector<int> tour1r = tour1; vector<int> tour2r = tour2; vector<int> cycle1r = cycle1; vector<int> cycle2r = cycle2; reverse(tour1r.begin(), tour1r.end()); reverse(tour2r.begin(), tour2r.end()); reverse(cycle1r.begin(), cycle1r.end()); reverse(cycle2r.begin(), cycle2r.end()); if(group_id[cycle1[0]] == group_id[cycle2[0]]) { cout << -1 << endl; for(int i : tour1) ans.push_back(i); for(int i : cycle1) ans.push_back(i); for(int i : tour1r) ans.push_back(i); for(int i : tour2) ans.push_back(i); for(int i : cycle2r) ans.push_back(i); for(int i : tour2r) ans.push_back(i); //ans.push_back(-2); //for(int i : cycle1) ans.push_back(i); //ans.push_back(-3); //for(int i : cycle2) ans.push_back(i); } else { return false; for(int i : tour1) ans.push_back(i); for(int i : cycle1) ans.push_back(i); for(int i : tour1r) ans.push_back(i); for(int i : tour2) ans.push_back(i); for(int i : cycle2) ans.push_back(i); for(int i : tour2r) ans.push_back(i); for(int i : tour1) ans.push_back(i); for(int i : cycle1r) ans.push_back(i); for(int i : tour1r) ans.push_back(i); for(int i : tour2) ans.push_back(i); for(int i : cycle2r) ans.push_back(i); for(int i : tour2r) ans.push_back(i); //ans.push_back(-1); } return true; } std::variant<bool, std::vector<int>> find_journey(int _N, int M, std::vector<int> U, std::vector<int> V) { N = _N; for(int i = 0; i < N; i++) { graph[i].clear(); bck[i].clear(); is_cycle[i] = false; vis[i] = false; group_id[i] = -1; } groups.clear(); for(int i = 0; i < M; i++) { graph[U[i]].push_back({V[i], i}); bck[V[i]].push_back({U[i], i}); } topo.clear(); for(int i = 0; i < N; i++) vis[i] = false; dfs(0); for(int i = 0; i < N; i++) vis[i] = false; reverse(topo.begin(), topo.end()); cur_group_id = -1; for(int i : topo) { if(vis[i]) continue; cur_group_id++; groups.push_back({}); dfs2(i); } for(int i = 0; i < N; i++) vis[i] = false; for(int i = 0; i < groups.size(); i++) { if(groups[i].size() == 1) continue; int tmp = groups[i][0]; while(!vis[tmp]) { vis[tmp] = true; for(auto [nxt, id] : graph[tmp]) { if(group_id[nxt] != group_id[tmp]) continue; cycle_next[tmp] = {nxt, id}; tmp = nxt; break; } } int tmp2 = tmp; do { is_cycle[tmp2] = true; tmp2 = cycle_next[tmp2].first; } while(tmp2 != tmp); } //for(int i = 0; i < N; i++) { // cout << cycle_next[i].first << " " << cycle_next[i].second << endl; //} for(int bit = (1<<17); bit >= 1; bit >>= 1) { if(test_cycle(bit)) return ans; } return 0; }

컴파일 시 표준 에러 (stderr) 메시지

islands.cpp: In function 'bool test_cycle(int)':
islands.cpp:61:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   61 |   while(qidx < q.size()) {
      |         ~~~~~^~~~~~~~~~
islands.cpp: In function 'std::variant<bool, std::vector<int, std::allocator<int> > > find_journey(int, int, std::vector<int>, std::vector<int>)':
islands.cpp:155:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  155 |  for(int i = 0; i < groups.size(); i++) {
      |                 ~~^~~~~~~~~~~~~~~
islands.cpp:179:9: error: could not convert '0' from 'int' to 'std::variant<bool, std::vector<int, std::allocator<int> > >'
  179 |  return 0;
      |         ^
      |         |
      |         int