Submission #649227

#	Time	Username	Problem	Language	Result	Execution time	Memory
649227		blue	Thousands Islands (IOI22_islands)	C++17	100 / 100	145 ms	21836 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)
		{
			// 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;
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;

		// cerr << "#\n";
 
		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)
		{
			// cerr << "??\n";
			nodecyc2.push_back(v);
			cyc2.push_back(vp.second);

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

			// cerr <
 
			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);
			// cerr << "reached end\n";
		}
		else if(nodevis[v] == 1 && !cyclic[v])
		{
			// cerr << "^^^\n";
			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])
		{
			// cerr << "hello\n";
			samecycle = 1;
			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;
	}
}
 
 
void testarray(vi U, vi V, vi res)
{
	vi inv(M, 0);

	int lst = -1;

	int loc = 0;

	string err;

	for(int r : res)
	{

		if(U[r] != loc && V[r] != loc)
			err = "Canoe doesn't travel to current source";
		else if(U[r] != loc)
			err = "Canoe not currently docked at source";
		else if(lst == r)
			err = "Canoe used consecutively";


		cerr << "take " << r << " : " << U[r] << " -> " << V[r] << '\n';

		if(!err.empty())
		{
			cerr << err << '\n';
			while(1);
		}



		loc = V[r];
		swap(U[r], V[r]);
		inv[r] = !inv[r];
		lst = r;
	}

	if(loc != 0)
		err = "Didn't return to 0";

	for(int j = 0; j < M; j++)
		if(inv[j])
			err = "Canoe not docked at initial location";

	if(!err.empty())
	{
		cerr << err << '\n';
		while(1);
	}
}
 
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 << "\n\n\n";

	// cerr << "nodelst2 = ";
	// for(int p : nodelst2)
	// 	cerr << p << ' ';
	// cerr << '\n';
	// cerr << "nodecyc2 = ";
	// for(int p : nodecyc2)
	// 	cerr << p << ' ';
	// cerr << '\n';
 
	// cerr << "lst2 = ";
	// for(int p : lst2)
	// 	cerr << p << ' ';
	// cerr << '\n';
	// cerr << "cyc2 = ";
	// for(int p : cyc2)
	// 	cerr << p << ' ';
	// cerr << '\n';


 
 
 
 
 
// cerr << "D\n";
 
	vi res;
 
	if(!samecycle)
	{
		// cerr << "diff cycle\n";
		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
	{
		// cerr << "samecycle\n";
		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";

	// testarray(U, V, res);
	
	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:397:8: warning: 'newsrc' may be used uninitialized in this function [-Wmaybe-uninitialized]
  397 |    src = newsrc;
      |    ~~~~^~~~~~~~

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