Submission #649231

#	Time	Username	Problem	Language	Result	Execution time	Memory
649231		blue	Thousands Islands (IOI22_islands)	C++17	100 / 100	141 ms	21872 KiB

islands

#include "islands.h"
#include <bits/stdc++.h>
using namespace std;
 
using vi = vector<int>;
using pii = pair<int, int>;
using vpii = vector<pii>;
#define sz(x) int(x.size())
 
const int mx = 100'000;
 
vpii edge[mx];
vpii revedge[mx];
 
int N, M;
 
queue<int> tbv;
 
int src = 0;
 
vi pushed(mx, 0);
vi killed(mx, 0);
 
vi outdeg(mx, 0);
 
vi incedge(mx, -1);
 
void addvec(vi& a, vi& b)
{
	for(int u : b)
		a.push_back(u);
}
 
void rev(vi& a)
{
	reverse(a.begin(), a.end());
}
 
void addrev(vi& a, vi& b)
{
	rev(b);
	addvec(a, b);
	rev(b);
}
 
 
vi nodevis(mx, 0);
vi cyclic(mx, 0);
 
bool samecycle = 0;
 
 
vi lst1, nodelst1, cyc1, nodecyc1;
 
int bannededge;
 
 
void dfs1(int u)
{
	for(pii vp : edge[u])
	{
		int v = vp.first;
 
		if(killed[v])
			continue;
 
		if(nodevis[v] == 0)
		{
			lst1.push_back(vp.second);
			nodelst1.push_back(vp.first);
 
			if(u == src)
				bannededge = vp.second;
 
			nodevis[v] = 1;
			dfs1(v);
		}
		else if(nodevis[v] == 1)
		{
			// samecycle = 1;
			nodecyc1.push_back(v);
			cyclic[v] = 1;
			cyc1.push_back(vp.second);
 
			while(1)
			{
				if(nodelst1.back() == v)
					break;
 
				nodecyc1.push_back(nodelst1.back());
				cyclic[nodelst1.back()] = 1;
				cyc1.push_back(lst1.back());
 
				nodelst1.pop_back();
				lst1.pop_back();
 
				
			}
			rev(nodecyc1);
			rev(cyc1);
		}
		return;
	}
}
 
vi lst2, cyc2, nodelst2, nodecyc2;
 
void dfs2(int u)
{
	for(pii vp : edge[u])
	{
		if(vp.second == bannededge)
			continue;
 
		int v = vp.first;


		if(killed[v])
			continue;

 
		if(nodevis[v] == 0)
		{
			lst2.push_back(vp.second);
			nodelst2.push_back(vp.first);
 
			if(u == src)
				bannededge = vp.second;
 
			nodevis[v] = 2;
			dfs2(v);
		}
		else if(nodevis[v] == 2)
		{
			nodecyc2.push_back(v);
			cyc2.push_back(vp.second);

			while(1)
			{
				if(nodelst2.back() == v)
					break;
 
				nodecyc2.push_back(nodelst2.back());
				cyc2.push_back(lst2.back());
 
				nodelst2.pop_back();
				lst2.pop_back();
			}
			rev(nodecyc2);
			rev(cyc2);
		}
		else if(nodevis[v] == 1 && !cyclic[v])
		{
			samecycle = 1;
			nodecyc2 = nodecyc1;
			cyc2 = cyc1;

			// cerr << "no"

			int id = 0;
			while(nodelst1[id] != v)
				id++;

			nodelst2.push_back(v);
			lst2.push_back(vp.second);

			for(id++; id < sz(nodelst1); id++)
			{
				nodelst2.push_back(nodelst1[id]);
				lst2.push_back(lst1[id-1]);
			}
		}
		else if(nodevis[v] == 1 && cyclic[v])
		{
			samecycle = 1;
			lst2.push_back(vp.second);
 
			int z = 0;
			while(nodecyc1[z] != v)
				z++;
 
			for(int f = z+1; f < sz(cyc1); f++)
			{
				cyc2.push_back(cyc1[f]);
				nodecyc2.push_back(nodecyc1[f]);
			}
			for(int f = 0; f <= z; f++)
			{
				cyc2.push_back(cyc1[f]);
				nodecyc2.push_back(nodecyc1[f]);
			}
		}
		return;
	}
}
 
variant<bool, vi> find_journey(int N_, int M_, vi U, vi V)
{
	N = N_;
	M = M_;
 
	for(int j = 0; j < M; j++)
	{
		edge[U[j]].push_back({V[j], j});
		revedge[V[j]].push_back({U[j], j});
		outdeg[U[j]]++;
	}
 
	for(int i = 0; i < N; i++)
	{
		if(outdeg[i] == 0)
		{
			pushed[i] = 1;
			tbv.push(i);
		}
	}
 
	if(pushed[src])
	{
		return false;
	}
 
 
	vi originlist;
 
 
	while(1)
	{
		if(!tbv.empty())
		{
			int u = tbv.front();
			tbv.pop();
			killed[u] = 1;
 
			for(pii vp : revedge[u])
			{	
				int v = vp.first;
				outdeg[v]--;
				if(outdeg[v] == 0)
				{
					pushed[v] = 1;
					if(v == src)
					{
						// gettime();
						return false;
					}
					tbv.push(v);
				}
			}
		}
		else if(outdeg[src] == 1)
		{
			int newsrc;
			for(pii vp : edge[src])
			{
				if(!pushed[vp.first])
				{
					newsrc = vp.first;
					incedge[newsrc] = vp.second;
					originlist.push_back(vp.second);
					break;
				}
			}
 
 
			pushed[src] = 1;
			killed[src] = 1;
			for(pii vp : revedge[src])
			{
				int v = vp.first;
				if(vp.second == incedge[src])
					continue;

				outdeg[v]--;
				if(outdeg[v] == 0)
				{
					pushed[v] = 1;
					if(pushed[newsrc])
						return false;
					tbv.push(v);
				}
			}
 
			src = newsrc;
		}
		else
		{
			break;
		}
	}
 
 
 
	nodevis[src] = 1;
	nodelst1.push_back(src);
	dfs1(src);
 
 
	nodelst2.push_back(src);
	dfs2(src);

 
	vi res;
 
	if(!samecycle)
	{
		addvec(res, originlist);
 
		addvec(res, lst1);
		addvec(res, cyc1);
		addrev(res, lst1);
 
		addvec(res, lst2);
		addvec(res, cyc2);
		addrev(res, lst2);
 
		addvec(res, lst1);
		addrev(res, cyc1);
		addrev(res, lst1);
		
		addvec(res, lst2);
		addrev(res, cyc2);
		addrev(res, lst2);
 
		addrev(res, originlist);
	}
	else
	{
		addvec(res, originlist);
 
		addvec(res, lst1);
		addvec(res, cyc1);
		addrev(res, lst1);
 
		addvec(res, lst2);
		addrev(res, cyc2);
		addrev(res, lst2);
 
		addrev(res, originlist);
	}
	
	return res;
}

Compilation message (stderr)

islands.cpp: In function 'std::variant<bool, std::vector<int, std::allocator<int> > > find_journey(int, int, vi, vi)':
islands.cpp:284:8: warning: 'newsrc' may be used uninitialized in this function [-Wmaybe-uninitialized]
  284 |    src = newsrc;
      |    ~~~~^~~~~~~~

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