Submission #648947

#	Time	Username	Problem	Language	Result	Execution time	Memory
648947		blue	Thousands Islands (IOI22_islands)	C++17	35 / 100	131 ms	17912 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";
}

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;
	}

	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;
					break;
				}
			}


			pushed[src] = 1;
			killed[src] = 1;
			originlist.push_back(src);
			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;
		}
	}
	// for(int j = 1; j <= 500'000; j++)
	// 	cerr << "hello world\n";
	return true;
}

Compilation message (stderr)

islands.cpp: In function 'std::variant<bool, std::vector<int, std::allocator<int> > > find_journey(int, int, vi, vi)':
islands.cpp:124:22: warning: 'newsrc' may be used uninitialized in this function [-Wmaybe-uninitialized]
  124 |      if(pushed[newsrc])
      |                      ^

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