Submission #638315

#	Time	Username	Problem	Language	Result	Execution time	Memory
638315		jamezzz	Thousands Islands (IOI22_islands)	C++17	24 / 100	100 ms	25744 KiB

islands

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

#define maxn 100005
#define pb push_back
#define pf push_front
#define ppb pop_back
#define ppf pop_front

int vis[maxn];
vector<int> AL[maxn];
deque<int> ans;
vector<int> s;
map<int,int> to[maxn];
map<int,int> to2[maxn];

bool dfs(int u,int p){
	vis[u]=1;
	s.pb(u);
	for(int v:AL[u]){
		if(vis[v]==2)continue;
		if(vis[v]==0){
			if(dfs(v,u)){
				ans.pf(to[u][v]);
				ans.pb(to[u][v]);
				s.ppb();
				vis[u]=2;
				return true;
			}
		}
		else{
			vector<int> st;
			bool found=false;
			for(int i=0;i<s.size();++i){
				if(s[i]==v)found=true;
				if(found)st.push_back(s[i]);
			}
			ans.pb(to[u][v]);
			for(int i=0;i<st.size()-1;++i){
				ans.pb(to2[st[i]][st[i+1]]);
			}
			ans.pb(to2[u][v]);
			ans.pb(to[u][v]);
			for(int i=st.size()-2;i>=0;--i){
				ans.pb(to2[st[i]][st[i+1]]);
			}
			ans.pb(to2[u][v]);
			s.ppb();
			vis[u]=2;
			return true;
		}
	}
	s.ppb();
	vis[u]=2;
	return false;
}

variant<bool,vector<int>> find_journey(int N,int M,vector<int> U,vector<int> V){
	for(int i=0;i<M;++i){
		AL[U[i]].pb(V[i]);
		if(to[U[i]].find(V[i])!=to[U[i]].end())to2[U[i]][V[i]]=i;
		else to[U[i]][V[i]]=i;
	}
	if(dfs(0,-1)){
		vector<int> res;
		for(int i:ans)res.pb(i);
		return res;
	}
	return false;
}

Compilation message (stderr)

islands.cpp: In function 'bool dfs(int, int)':
islands.cpp:35:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   35 |    for(int i=0;i<s.size();++i){
      |                ~^~~~~~~~~
islands.cpp:40:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   40 |    for(int i=0;i<st.size()-1;++i){
      |                ~^~~~~~~~~~~~

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