제출 #674075

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
674075		US3RN4M3	수천개의 섬 (IOI22_islands)	C++17	3.50 / 100	1091 ms	16048 KiB

islands

#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 false;
}

컴파일 시 표준 에러 (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++) {
      |                 ~~^~~~~~~~~~~~~~~

• Subtask 1: 1.75 / 5
• Subtask 2: 1.75 / 5
• Subtask 3: 0 / 21
• Subtask 4: 0 / 24
• Subtask 5: 0 / 45