제출 #1028191

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1028191		42kangaroo	수천개의 섬 (IOI22_islands)	C++17	6.75 / 100	21 ms	6360 KiB

islands

#include "islands.h"

#include <variant>
#include <vector>
#include "bits/stdc++.h"

using namespace std;

using g_t = vector<vector<pair<int,int>>>;

int dfs(int n, int p, g_t& g, vector<bool>& vis, vector<int>& re) {
	vis[n] = true;
	for (auto [ne, nu]: g[n]) {
		if (nu/2 == p/2) continue;
		if (vis[ne]) {
			re.push_back(nu);
			return ne;
		}
		int res = dfs(ne, nu, g, vis, re);
		if (re.empty()) continue;
		re.push_back(nu);
		if (res == n) {
			re.push_back(-1);
			return -2;
		}
		return res;
	}
	return -2;
}

std::variant<bool, std::vector<int>> find_journey(
		int N, int M, std::vector<int> U, std::vector<int> V) {
	if (N == 2) {
		vector<int> s0, s1;
		for (int i = 0; i < M; ++i) {
			if (U[i] == 0) s0.push_back(i);
			else s1.push_back(i);
		}
		if (s0.size() >= 2 && s1.size() >= 1) {
			return vector<int>{s0[0], s1[0], s0[1], s0[0], s1[0], s0[1]};
		} else return false;
	}
	g_t g(N);
	for (int i = 0; i < M / 2; ++i) {
		g[U[2*i]].push_back({V[2*i], 2*i});
		g[V[2*i]].push_back({U[2*i], 2*i + 1});
	}
	vector<int> intr;
	vector<bool> vis(N, false);
	dfs(0, -2, g, vis, intr);
	if (intr.empty()) return false;
	vector<int> res;
	int lim = intr.size() - 1;
	for (int i = intr.size() - 1; intr[i] != -1; --i) {
		res.push_back(intr[i]);
		lim = i - 1;
	}
	if (U[0] == U[1]) {
		for (int i = lim - 1; i >= 0; --i) {
			res.push_back(2*intr[i]);
		}
		for (int i = lim - 1; i >= 0; --i) {
			res.push_back(2*intr[i]);
		}
		for (int i = 0; i < lim; ++i) {
			res.push_back(2*intr[i] + 1);
		}
		for (int i = 0; i < lim; ++i) {
			res.push_back(2*intr[i] + 1);
		}
	} else {
		for (int i = lim - 1; i >= 0; --i) {
			res.push_back(intr[i]);
		}
		for (int i = 0; i < lim; ++i) {
			res.push_back(intr[i] - (2*(intr[i]%2) - 1));
		}
		for (int i = 0; i < lim; ++i) {
			res.push_back(intr[i]);
		}
		for (int i = lim - 1; i >= 0; --i) {
			res.push_back(intr[i] - (2*(intr[i]%2) - 1));
		}
	}
	for (int i = lim + 1; i < intr.size(); ++i) {
		res.push_back(intr[i]);
	}
	return res;
}

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

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:85:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   85 |  for (int i = lim + 1; i < intr.size(); ++i) {
      |                        ~~^~~~~~~~~~~~~

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