Submission #831187

#	Time	Username	Problem	Language	Result	Execution time	Memory
831187		caganyanmaz	Thousands Islands (IOI22_islands)	C++17	24 / 100	34 ms	8788 KiB

islands

#include <bits/stdc++.h>
#define pb push_back
#include "islands.h"
using namespace std;


#ifdef DEBUGGING
#include "../debug.h"
#else
#define debug(x...) void(42)
#endif

constexpr static int MXN = 1e5 + 5;
int n, m;
vector<int> u, v;
vector<array<int, 2>> g[MXN];
int state[MXN];
vector<int> path;

bool dfs(int node)
{
	state[node] = 1;
	for (auto [c, e] : g[node])
	{
		path.pb(e);
		if (state[c] == 1)
			return true;
		if (state[c] == 0 && dfs(c))
			return true;
		path.pop_back();
	}
	state[node] = 2;
	return false;
}

variant<bool, vector<int>> find_journey(int N, int M, vector<int> U, vector<int> V)
{
	n = N, m = M;
	u = U, v = V;
	for (int i = 0; i < m; i+=2)
		g[u[i]].pb({v[i], i});
	if(!dfs(0))
		return false;
	int lsn = v[path.back()];
	vector<int> res;
	int i;
	for (i = path.size()-2; i >= 0 && v[path[i]] != lsn; i--);
	for (int j = 0; j <= i; j++)
		res.pb(path[j]);
	for (int j = i+1; j < path.size(); j++)
		res.pb(path[j]);
	for (int j = i+1; j < path.size(); j++)
		res.pb(path[j]+1);
	for (int j = path.size()-1; j > i; j--)
		res.pb(path[j]);
	for (int j = path.size()-1; j > i; j--)
		res.pb(path[j]+1);
	for (int j = i; j >= 0; j--)
		res.pb(path[j]);
	return res;

}

Compilation message (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:50:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   50 |  for (int j = i+1; j < path.size(); j++)
      |                    ~~^~~~~~~~~~~~~
islands.cpp:52:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   52 |  for (int j = i+1; j < path.size(); j++)
      |                    ~~^~~~~~~~~~~~~

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