Submission #693901

#	Time	Username	Problem	Language	Result	Execution time	Memory
693901		Pyqe	Thousands Islands (IOI22_islands)	C++17	9.10 / 100	51 ms	12508 KiB

islands

#include <bits/stdc++.h>
#include "islands.h"

using namespace std;

#define mp make_pair
#define fr first
#define sc second

const long long inf=1e18;
long long n,m,nn=0,nm=0,pr[100069],pe[100069],ca[100069],ca2[100069];
pair<long long,long long> ed[100069];
vector<pair<long long,long long>> al[100069];
bitset<100069> vtd;

void dfs(long long x)
{
	long long i,sz=al[x].size(),l,p;
	
	vtd[x]=1;
	for(i=0;i<sz;i++)
	{
		l=al[x][i].fr;
		p=al[x][i].sc;
		if(!vtd[l])
		{
			pr[l]=x;
			pe[l]=p;
			dfs(l);
		}
	}
}

variant<bool,vector<int>> find_journey(int on,int om,vector<int> ka,vector<int> la)
{
	long long i,j,k,l,p;
	vector<int> sq;
	
	n=on;
	m=om;
	for(i=1;i<=m;i++)
	{
		k=ka[i-1]+1;
		l=la[i-1]+1;
		ed[i]={k,l};
		al[k].push_back({l,i-1});
	}
	dfs(1);
	for(i=1;i<=n;i++)
	{
		if(vtd[i]&&(al[i].size()>=3||i==1&&al[i].size()>=2))
		{
			for(p=i;p!=1;p=pr[p])
			{
				nn++;
				ca[nn]=pe[p];
			}
			for(j=0;1;j++)
			{
				l=al[i][j].fr;
				p=al[i][j].sc;
				if(i==1||p!=(pe[i]^1))
				{
					nm++;
					ca2[nm]=p;
					if(nm==2)
					{
						break;
					}
				}
			}
			for(j=nn;j;j--)
			{
				sq.push_back(pe[j]);
			}
			sq.push_back(ca2[1]);
			sq.push_back(ca2[1]^1);
			sq.push_back(ca2[2]);
			sq.push_back(ca2[2]^1);
			sq.push_back(ca2[1]^1);
			sq.push_back(ca2[1]);
			sq.push_back(ca2[2]^1);
			sq.push_back(ca2[2]);
			for(j=1;j<=nn;j++)
			{
				sq.push_back(pe[j]);
			}
			break;
		}
	}
	if(i>n)
	{
		return false;
	}
	return sq;
}

Compilation message (stderr)

islands.cpp: In function 'std::variant<bool, std::vector<int, std::allocator<int> > > find_journey(int, int, std::vector<int>, std::vector<int>)':
islands.cpp:51:36: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   51 |   if(vtd[i]&&(al[i].size()>=3||i==1&&al[i].size()>=2))
      |                                ~~~~^~~~~~~~~~~~~~~~~

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