Submission #648958

#	Time	Username	Problem	Language	Result	Execution time	Memory
648958		blue	Thousands Islands (IOI22_islands)	C++17	10.85 / 100	431 ms	15060 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 gettime()
{
	for(int j = 1; j <= 500'000; j++)
		cerr << "hello world\n";
}

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;
vi nodelst1;

vi cyc1;
vi 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)
		{
			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;
vi cyc2;
vi nodelst2;
vi nodecyc2;

void dfs2(int u)
{
	cerr << "dfs2 " << u << '\n';
	for(pii vp : edge[u])
	{
		if(vp.second == bannededge)
			continue;

		int v = vp.first;

		cerr << u << " -> " << v << " via " << vp.second << '\n';

		cerr << cyclic[v] << ' ' << nodevis[v] << '\n';

		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 || (nodevis[v] == 1 && !cyclic[v]))
		{
			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])
		{
			cerr << "hello\n";
			lst2.push_back(vp.second);

			int z = 0;
			while(nodecyc1[z] != v)
				z++;

			cerr << "v = " << v << '\n';

			cerr << "nodecyc1 = ";
			for(int y : nodecyc1)
				cerr << y << ' ';
			cerr << '\n';

			cerr << "cyc1 = ";
			for(int y : cyc1)
				cerr << y << ' ';
			cerr << '\n';

			cerr << "z = " << z << '\n';

			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])
	{
		// gettime();
		return false;
	}

	cerr << "A\n";

	vi originlist;

	// cerr << sz(tbv) << " ! \n";

	// cerr << "outdeg 1 = " << outdeg[1] << '\n';

	while(1)
	{
		if(!tbv.empty())
		{
			int u = tbv.front();
			tbv.pop();
			killed[u] = 1;

			for(pii vp : revedge[u])
			{	
				int v = vp.first;
				// cerr << "remove out edge from " << v << " to del node = " << u << ", edge ind = " << vp.second << '\n';

				outdeg[v]--;
				// cerr << "outdeg " << v << " = " << outdeg[v] << '\n';
				if(outdeg[v] == 0)
				{
					pushed[v] = 1;
					if(v == src)
					{
						// gettime();
						return false;
					}
					tbv.push(v);
					// cerr << "push " << v << " to killing queue\n";
				}
			}
		}
		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;
				// cerr << "remove out edge from " << v << " to src = " << src << ", edge ind = " << vp.second << '\n';

				outdeg[v]--;
				// cerr << "outdeg " << v << " = " << outdeg[v] << '\n';
				if(outdeg[v] == 0)
				{
					pushed[v] = 1;
					if(pushed[newsrc])
						return false;
					tbv.push(v);
					// cerr << "push " << v << " to killing queue\n";
				}
			}

			cerr << src << " -> " << newsrc << '\n';
			src = newsrc;
		}
		else
		{
			break;
		}
	}
	cerr << "B\n";
	cerr << "src = " << src << '\n';



	nodevis[src] = 1;
	nodelst1.push_back(src);
	dfs1(src);

	cerr << "nodelst1 = ";
	for(int p : nodelst1)
		cerr << p << ' ';
	cerr << '\n';
	cerr << "nodecyc1 = ";
	for(int p : nodecyc1)
		cerr << p << ' ';
	cerr << '\n';

	cerr << "lst1 = ";
	for(int p : lst1)
		cerr << p << ' ';
	cerr << '\n';
	cerr << "cyc1 = ";
	for(int p : cyc1)
		cerr << p << ' ';
	cerr << '\n';

	cerr << "C\n";

	cerr << "bannededge = " << bannededge << '\n';


	nodelst2.push_back(src);
	dfs2(src);





cerr << "D\n";

	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);
	}
	cerr << "E\n";
	
	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:315:39: warning: 'newsrc' may be used uninitialized in this function [-Wmaybe-uninitialized]
  315 |    cerr << src << " -> " << newsrc << '\n';
      |                                       ^~~~

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