Submission #987087

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
987087	2024-05-21T20:29:32 Z	Pyqe	Thousands Islands (IOI22_islands)	C++17	35 / 100	98 ms	41300 KB

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,nn2[2],nn3[2],cnn,dh[100069],an[100069],cyc[100069],ex[100069],ex2[2][100069],ex3[2][100069],cex[100069];
vector<pair<long long,long long>> al[100069],nx[100069],nx2[100069];
vector<long long> vl[100069];
bitset<100069> vtd,vtd2;
pair<long long,long long> pr[100069];
bitset<200069> spc[2];

void dfs(long long x)
{
	long long i,j,sz=al[x].size(),sz2,k,l,p;
	
	vtd[x]=1;
	vtd2[x]=1;
	for(i=0;i<sz;i++)
	{
		l=al[x][i].fr;
		p=al[x][i].sc;
		if(!vtd[l])
		{
			dh[l]=dh[x]+1;
			pr[l]={x,p};
			dfs(l);
		}
		if(vtd2[l])
		{
			if(dh[l]>dh[an[x]]&&!cyc[x])
			{
				an[x]=l;
				nx[x]={{l,p}};
			}
		}
		else
		{
			cyc[x]=min(cyc[x]+cyc[l],2ll);
			if(cyc[l])
			{
				nx2[x].push_back({l,p});
			}
			if(vl[x].empty())
			{
				if(dh[an[l]]>dh[an[x]]&&!cyc[x])
				{
					an[x]=an[l];
					nx[x]={{l,p}};
				}
			}
			else
			{
				if(!cyc[l])
				{
					if(!cyc[x])
					{
						nx[x].clear();
					}
					cyc[x]=min(cyc[x]+1,2ll);
					nx[x].push_back({l,p});
				}
				sz2=vl[x].size();
				for(j=0;j<sz2;j++)
				{
					k=vl[x][j];
					cyc[k]=max(cyc[k],1ll);
				}
				vl[x].clear();
			}
		}
	}
	vtd2[x]=0;
	if(vtd2[an[x]])
	{
		vl[an[x]].push_back(x);
	}
}

variant<bool,vector<int>> find_journey(int on,int om,vector<int> ka,vector<int> la)
{
	long long i,ii,k,l,p,sz,e,kk,ll,rt=0;
	pair<long long,long long> mne={inf,-1};
	vector<int> sq;
	
	n=on;
	m=om;
	for(i=1;i<=m;i++)
	{
		k=ka[i-1]+1;
		l=la[i-1]+1;
		al[k].push_back({l,i});
	}
	dh[0]=-1;
	dfs(1);
	if(cyc[1]!=2)
	{
		return false;
	}
	for(i=1;i<=n;i++)
	{
		if(cyc[i]==2&&dh[i]>dh[rt])
		{
			rt=i;
		}
	}
	for(k=rt;k!=1;k=pr[k].fr)
	{
		p=pr[k].sc;
		nn++;
		ex[nn]=p;
	}
	reverse(ex+1,ex+nn+1);
	for(ii=0;ii<2;ii++)
	{
		for(k=rt;!nx2[k].empty();k=l)
		{
			l=nx2[k].back().fr;
			p=nx2[k].back().sc;
			nx2[k].pop_back();
			nn2[ii]++;
			ex2[ii][nn2[ii]]=p;
		}
		for(i=1;i<=n;i++)
		{
			reverse(nx[i].begin(),nx[i].end());
		}
		mne=min(mne,{dh[ll],ii});
	}
	return true;
	for(ii=0;ii<2;ii++)
	{
		for(i=1;i<=nn3[ii];i++)
		{
			k=ex3[ii][i];
			spc[ii][k]=1;
		}
	}
	for(i=1;i<=nn3[1];i++)
	{
		k=ex3[1][i];
		if(!spc[0][k])
		{
			break;
		}
	}
	if(nn3[0]==nn3[1]&&i>nn3[0])
	{
		for(i=1;i<=nn;i++)
		{
			sq.push_back(ex[i]);
		}
		for(i=1;i<=nn2[0];i++)
		{
			sq.push_back(ex2[0][i]);
		}
		for(i=1;i<=nn3[0];i++)
		{
			sq.push_back(ex3[0][i]);
		}
		for(i=nn2[0];i;i--)
		{
			sq.push_back(ex2[0][i]);
		}
		for(i=1;i<=nn2[1];i++)
		{
			sq.push_back(ex2[1][i]);
		}
		for(i=nn3[1];i;i--)
		{
			sq.push_back(ex3[1][i]);
		}
		for(i=nn2[1];i;i--)
		{
			sq.push_back(ex2[1][i]);
		}
		for(i=nn;i;i--)
		{
			sq.push_back(ex[i]);
		}
	}
	else
	{
		for(i=1;i<=nn3[1];i++)
		{
			k=ex3[1][i];
			if(spc[0][k])
			{
				break;
			}
		}
		if(i<=nn3[1])
		{
			e=mne.sc;
			for(i=1;i<=nn;i++)
			{
				sq.push_back(ex[i]);
			}
			for(i=1;i<=nn2[!e];i++)
			{
				sq.push_back(ex2[!e][i]);
			}
			for(i=1;i<=nn3[!e];i++)
			{
				sq.push_back(ex3[!e][i]);
			}
			for(i=nn2[!e];i;i--)
			{
				sq.push_back(ex2[!e][i]);
			}
			for(i=1;i<=nn2[e];i++)
			{
				sq.push_back(ex2[e][i]);
			}
			for(i=1;i<=nn3[e];i++)
			{
				k=ex3[e][i];
				if(spc[!e][k])
				{
					break;
				}
				sq.push_back(k);
			}
			kk=i;
			for(i=1;ex3[!e][i]!=k;i++);
			for(i=(i+nn3[!e]-2)%nn3[!e]+1;1;i=(i+nn3[!e]-2)%nn3[!e]+1)
			{
				k=ex3[!e][i];
				if(spc[e][k])
				{
					break;
				}
				sq.push_back(k);
			}
			for(i=kk;i<=nn3[e];i++)
			{
				k=ex3[e][i];
				if(!spc[!e][k])
				{
					sq.push_back(k);
				}
			}
			for(i=nn2[e];i;i--)
			{
				sq.push_back(ex2[e][i]);
			}
			for(i=1;i<=nn2[!e];i++)
			{
				k=ex2[!e][i];
				if(spc[e][k])
				{
					break;
				}
				sq.push_back(k);
			}
			if(i<=nn2[!e])
			{
				kk=k;
			}
			else
			{
				kk=ex3[!e][1];
			}
			for(i=1;ex3[e][i]!=kk;i++);
			for(i=(i+nn3[e]-2)%nn3[e]+1;1;i=(i+nn3[e]-2)%nn3[e]+1)
			{
				k=ex3[e][i];
				sq.push_back(k);
				if(k==kk)
				{
					break;
				}
			}
			for(i=nn2[!e];i;i--)
			{
				k=ex2[!e][i];
				if(!spc[e][k])
				{
					sq.push_back(k);
				}
			}
			for(i=nn;i;i--)
			{
				sq.push_back(ex[i]);
			}
		}
		else
		{
			for(i=1;i<=nn;i++)
			{
				sq.push_back(ex[i]);
			}
			for(i=1;i<=nn2[0];i++)
			{
				sq.push_back(ex2[0][i]);
			}
			for(i=1;i<=nn3[0];i++)
			{
				sq.push_back(ex3[0][i]);
			}
			for(i=nn2[0];i;i--)
			{
				sq.push_back(ex2[0][i]);
			}
			for(i=1;i<=nn2[1];i++)
			{
				sq.push_back(ex2[1][i]);
			}
			for(i=1;i<=nn3[1];i++)
			{
				sq.push_back(ex3[1][i]);
			}
			for(i=nn2[1];i;i--)
			{
				sq.push_back(ex2[1][i]);
			}
			for(i=1;i<=nn2[0];i++)
			{
				sq.push_back(ex2[0][i]);
			}
			for(i=nn3[0];i;i--)
			{
				sq.push_back(ex3[0][i]);
			}
			for(i=nn2[0];i;i--)
			{
				sq.push_back(ex2[0][i]);
			}
			for(i=1;i<=nn2[1];i++)
			{
				sq.push_back(ex2[1][i]);
			}
			for(i=nn3[1];i;i--)
			{
				sq.push_back(ex3[1][i]);
			}
			for(i=nn2[1];i;i--)
			{
				sq.push_back(ex2[1][i]);
			}
			for(i=nn;i;i--)
			{
				sq.push_back(ex[i]);
			}
		}
	}
	sz=sq.size();
	for(i=0;i<sz;i++)
	{
		sq[i]--;
	}
	return sq;
}

Subtask #1

1.75 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	3 ms	12632 KB	Output is correct
2	Partially correct	3 ms	14684 KB	Output is partially correct
3	Correct	4 ms	12748 KB	Output is correct
4	Correct	3 ms	12632 KB	Output is correct
5	Correct	4 ms	12636 KB	Output is correct
6	Partially correct	4 ms	14684 KB	Output is partially correct
7	Partially correct	35 ms	22588 KB	Output is partially correct

Subtask #2

1.75 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Partially correct	4 ms	14680 KB	Output is partially correct
2	Correct	4 ms	12636 KB	Output is correct
3	Partially correct	4 ms	14684 KB	Output is partially correct
4	Partially correct	4 ms	14680 KB	Output is partially correct
5	Partially correct	3 ms	14684 KB	Output is partially correct
6	Partially correct	39 ms	22436 KB	Output is partially correct

Subtask #3

7.35 / 21.0

#	Verdict	Execution time	Memory	Grader output
1	Partially correct	5 ms	15192 KB	Output is partially correct
2	Correct	4 ms	12636 KB	Output is correct
3	Correct	3 ms	12636 KB	Output is correct
4	Partially correct	4 ms	14684 KB	Output is partially correct
5	Correct	4 ms	12892 KB	Output is correct
6	Partially correct	4 ms	14684 KB	Output is partially correct
7	Correct	4 ms	12636 KB	Output is correct
8	Partially correct	4 ms	14680 KB	Output is partially correct
9	Partially correct	4 ms	14684 KB	Output is partially correct
10	Partially correct	4 ms	15068 KB	Output is partially correct
11	Partially correct	4 ms	14684 KB	Output is partially correct
12	Partially correct	4 ms	14940 KB	Output is partially correct
13	Correct	3 ms	12632 KB	Output is correct
14	Correct	4 ms	12632 KB	Output is correct
15	Partially correct	3 ms	14684 KB	Output is partially correct
16	Correct	4 ms	12636 KB	Output is correct
17	Partially correct	23 ms	17752 KB	Output is partially correct
18	Partially correct	19 ms	17148 KB	Output is partially correct
19	Correct	4 ms	12636 KB	Output is correct
20	Partially correct	3 ms	14684 KB	Output is partially correct
21	Partially correct	5 ms	14780 KB	Output is partially correct
22	Partially correct	3 ms	14684 KB	Output is partially correct
23	Partially correct	33 ms	22356 KB	Output is partially correct

Subtask #4

8.4 / 24.0

#	Verdict	Execution time	Memory	Grader output
1	Partially correct	4 ms	14684 KB	Output is partially correct
2	Partially correct	5 ms	14940 KB	Output is partially correct
3	Partially correct	32 ms	21328 KB	Output is partially correct
4	Partially correct	34 ms	21840 KB	Output is partially correct
5	Partially correct	4 ms	14936 KB	Output is partially correct
6	Partially correct	5 ms	14936 KB	Output is partially correct
7	Partially correct	4 ms	14684 KB	Output is partially correct
8	Partially correct	4 ms	14684 KB	Output is partially correct
9	Partially correct	4 ms	14684 KB	Output is partially correct
10	Partially correct	5 ms	14940 KB	Output is partially correct
11	Correct	3 ms	12892 KB	Output is correct
12	Partially correct	6 ms	14940 KB	Output is partially correct
13	Partially correct	4 ms	14936 KB	Output is partially correct
14	Partially correct	4 ms	14940 KB	Output is partially correct
15	Partially correct	5 ms	14940 KB	Output is partially correct
16	Partially correct	4 ms	14940 KB	Output is partially correct
17	Correct	3 ms	12636 KB	Output is correct
18	Partially correct	6 ms	14940 KB	Output is partially correct
19	Partially correct	3 ms	14940 KB	Output is partially correct
20	Correct	36 ms	20052 KB	Output is correct
21	Partially correct	34 ms	21596 KB	Output is partially correct
22	Correct	3 ms	12888 KB	Output is correct
23	Correct	3 ms	12636 KB	Output is correct
24	Correct	5 ms	12636 KB	Output is correct
25	Partially correct	3 ms	14684 KB	Output is partially correct
26	Partially correct	5 ms	14940 KB	Output is partially correct
27	Partially correct	38 ms	22692 KB	Output is partially correct
28	Partially correct	38 ms	22700 KB	Output is partially correct
29	Correct	3 ms	12636 KB	Output is correct
30	Correct	37 ms	20984 KB	Output is correct
31	Partially correct	4 ms	14680 KB	Output is partially correct
32	Partially correct	36 ms	22456 KB	Output is partially correct
33	Partially correct	32 ms	21844 KB	Output is partially correct
34	Partially correct	23 ms	19800 KB	Output is partially correct
35	Partially correct	3 ms	14940 KB	Output is partially correct
36	Partially correct	29 ms	21188 KB	Output is partially correct
37	Partially correct	35 ms	24148 KB	Output is partially correct
38	Correct	4 ms	12632 KB	Output is correct
39	Correct	30 ms	19036 KB	Output is correct
40	Partially correct	5 ms	14940 KB	Output is partially correct
41	Correct	35 ms	21084 KB	Output is correct
42	Partially correct	34 ms	22616 KB	Output is partially correct
43	Correct	3 ms	12888 KB	Output is correct
44	Correct	4 ms	12892 KB	Output is correct
45	Partially correct	5 ms	14940 KB	Output is partially correct
46	Partially correct	19 ms	19036 KB	Output is partially correct

Subtask #5

15.75 / 45.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	3 ms	12632 KB	Output is correct
2	Partially correct	3 ms	14684 KB	Output is partially correct
3	Correct	4 ms	12748 KB	Output is correct
4	Correct	3 ms	12632 KB	Output is correct
5	Correct	4 ms	12636 KB	Output is correct
6	Partially correct	4 ms	14684 KB	Output is partially correct
7	Partially correct	35 ms	22588 KB	Output is partially correct
8	Partially correct	4 ms	14680 KB	Output is partially correct
9	Correct	4 ms	12636 KB	Output is correct
10	Partially correct	4 ms	14684 KB	Output is partially correct
11	Partially correct	4 ms	14680 KB	Output is partially correct
12	Partially correct	3 ms	14684 KB	Output is partially correct
13	Partially correct	39 ms	22436 KB	Output is partially correct
14	Partially correct	5 ms	15192 KB	Output is partially correct
15	Correct	4 ms	12636 KB	Output is correct
16	Correct	3 ms	12636 KB	Output is correct
17	Partially correct	4 ms	14684 KB	Output is partially correct
18	Correct	4 ms	12892 KB	Output is correct
19	Partially correct	4 ms	14684 KB	Output is partially correct
20	Correct	4 ms	12636 KB	Output is correct
21	Partially correct	4 ms	14680 KB	Output is partially correct
22	Partially correct	4 ms	14684 KB	Output is partially correct
23	Partially correct	4 ms	15068 KB	Output is partially correct
24	Partially correct	4 ms	14684 KB	Output is partially correct
25	Partially correct	4 ms	14940 KB	Output is partially correct
26	Correct	3 ms	12632 KB	Output is correct
27	Correct	4 ms	12632 KB	Output is correct
28	Partially correct	3 ms	14684 KB	Output is partially correct
29	Correct	4 ms	12636 KB	Output is correct
30	Partially correct	23 ms	17752 KB	Output is partially correct
31	Partially correct	19 ms	17148 KB	Output is partially correct
32	Correct	4 ms	12636 KB	Output is correct
33	Partially correct	3 ms	14684 KB	Output is partially correct
34	Partially correct	5 ms	14780 KB	Output is partially correct
35	Partially correct	3 ms	14684 KB	Output is partially correct
36	Partially correct	33 ms	22356 KB	Output is partially correct
37	Partially correct	4 ms	14680 KB	Output is partially correct
38	Correct	3 ms	12636 KB	Output is correct
39	Correct	4 ms	12788 KB	Output is correct
40	Correct	3 ms	12636 KB	Output is correct
41	Correct	18 ms	15960 KB	Output is correct
42	Correct	4 ms	12892 KB	Output is correct
43	Correct	46 ms	26760 KB	Output is correct
44	Correct	39 ms	23752 KB	Output is correct
45	Partially correct	43 ms	28988 KB	Output is partially correct
46	Partially correct	3 ms	14680 KB	Output is partially correct
47	Partially correct	3 ms	14680 KB	Output is partially correct
48	Partially correct	3 ms	14680 KB	Output is partially correct
49	Partially correct	6 ms	14940 KB	Output is partially correct
50	Partially correct	82 ms	41300 KB	Output is partially correct
51	Correct	79 ms	33868 KB	Output is correct
52	Correct	74 ms	36032 KB	Output is correct
53	Partially correct	77 ms	40388 KB	Output is partially correct
54	Correct	98 ms	37572 KB	Output is correct
55	Correct	92 ms	39616 KB	Output is correct
56	Partially correct	97 ms	40388 KB	Output is partially correct
57	Partially correct	51 ms	27584 KB	Output is partially correct
58	Partially correct	73 ms	33236 KB	Output is partially correct
59	Correct	68 ms	24660 KB	Output is correct
60	Correct	53 ms	26196 KB	Output is correct
61	Correct	46 ms	23120 KB	Output is correct
62	Correct	10 ms	14428 KB	Output is correct
63	Correct	50 ms	22612 KB	Output is correct
64	Partially correct	23 ms	20060 KB	Output is partially correct
65	Partially correct	3 ms	12636 KB	Output is partially correct
66	Partially correct	4 ms	14684 KB	Output is partially correct
67	Partially correct	89 ms	34908 KB	Output is partially correct
68	Correct	39 ms	22608 KB	Output is correct
69	Correct	43 ms	24404 KB	Output is correct
70	Partially correct	3 ms	14940 KB	Output is partially correct
71	Correct	44 ms	21332 KB	Output is correct
72	Partially correct	4 ms	14684 KB	Output is partially correct
73	Correct	62 ms	24032 KB	Output is correct
74	Partially correct	89 ms	36304 KB	Output is partially correct
75	Partially correct	7 ms	15448 KB	Output is partially correct
76	Partially correct	32 ms	25376 KB	Output is partially correct
77	Correct	70 ms	40388 KB	Output is correct
78	Correct	61 ms	26152 KB	Output is correct
79	Partially correct	4 ms	14684 KB	Output is partially correct
80	Partially correct	82 ms	33744 KB	Output is partially correct
81	Partially correct	4 ms	14940 KB	Output is partially correct
82	Correct	33 ms	20788 KB	Output is correct
83	Partially correct	4 ms	14680 KB	Output is partially correct
84	Partially correct	4 ms	14684 KB	Output is partially correct
85	Partially correct	32 ms	24536 KB	Output is partially correct
86	Partially correct	6 ms	14940 KB	Output is partially correct
87	Correct	3 ms	12892 KB	Output is correct
88	Partially correct	5 ms	15028 KB	Output is partially correct
89	Correct	60 ms	26092 KB	Output is correct
90	Correct	53 ms	23116 KB	Output is correct
91	Partially correct	79 ms	36348 KB	Output is partially correct
92	Partially correct	3 ms	14684 KB	Output is partially correct