Submission #1069690

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1069690	2024-08-22T08:17:50 Z	Muhammad_Aneeq	Longest Trip (IOI23_longesttrip)	C++17	40 / 100	993 ms	1376 KB

longesttrip

#include <vector>
#include <set>
#include "longesttrip.h"
#include <bitset>
using namespace std;
int const MAXN=256;
vector<int>nei[MAXN]={};
vector<int>ans;
vector<int>cur;
bitset<MAXN>vis;
void dfs(int u,int p=-1)
{
	vis[u]=1;
	cur.push_back(u);
	bool w=0;
	for (auto i:nei[u])
	{
		if (vis[i])
			continue;
		w=1;
		dfs(i,u);
	}
	if (w==0)
	{
		if (cur.size()>ans.size())
			ans=cur;
	}
	cur.pop_back();
}
vector<int> longest_trip(int N, int D)
{
	ans.clear();
	cur.clear();
	for (int i=0;i<N;i++)
		nei[i].clear();
	vector<int>x(1),y(1);
	for (int i=0;i<N;i++)
		for (int j=i+1;j<N;j++)
		{
			x[0]=i;y[0]=j;
			if (are_connected(x,y))
				nei[i].push_back(j),nei[j].push_back(i);
		}
	for (int i=0;i<N;i++)
	{
		for (int j=0;j<N;j++)
			vis[j]=0;
		dfs(i);
	}
	return ans;
}

Subtask #0

0.0 / 0.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	344 KB	Output is correct
2	Correct	204 ms	1064 KB	Output is correct

Subtask #1

5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	6 ms	344 KB	Output is correct
2	Correct	28 ms	344 KB	Output is correct
3	Correct	150 ms	344 KB	Output is correct
4	Correct	389 ms	740 KB	Output is correct
5	Correct	986 ms	944 KB	Output is correct

Subtask #2

10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	9 ms	344 KB	Output is correct
2	Correct	22 ms	344 KB	Output is correct
3	Correct	168 ms	600 KB	Output is correct
4	Correct	428 ms	712 KB	Output is correct
5	Correct	930 ms	784 KB	Output is correct
6	Correct	7 ms	344 KB	Output is correct
7	Correct	22 ms	344 KB	Output is correct
8	Correct	137 ms	344 KB	Output is correct
9	Correct	374 ms	344 KB	Output is correct
10	Correct	990 ms	1056 KB	Output is correct
11	Correct	838 ms	716 KB	Output is correct
12	Correct	827 ms	884 KB	Output is correct
13	Correct	820 ms	832 KB	Output is correct

Subtask #3

25.0 / 25.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	6 ms	344 KB	Output is correct
2	Correct	25 ms	344 KB	Output is correct
3	Correct	139 ms	344 KB	Output is correct
4	Correct	425 ms	592 KB	Output is correct
5	Correct	888 ms	1028 KB	Output is correct
6	Correct	7 ms	344 KB	Output is correct
7	Correct	21 ms	344 KB	Output is correct
8	Correct	161 ms	344 KB	Output is correct
9	Correct	306 ms	592 KB	Output is correct
10	Correct	899 ms	1000 KB	Output is correct
11	Correct	899 ms	1048 KB	Output is correct
12	Correct	926 ms	1004 KB	Output is correct
13	Correct	875 ms	1108 KB	Output is correct
14	Correct	7 ms	344 KB	Output is correct
15	Correct	10 ms	344 KB	Output is correct
16	Correct	45 ms	344 KB	Output is correct
17	Correct	97 ms	340 KB	Output is correct
18	Correct	147 ms	344 KB	Output is correct
19	Correct	325 ms	344 KB	Output is correct
20	Correct	326 ms	592 KB	Output is correct
21	Correct	942 ms	956 KB	Output is correct
22	Correct	922 ms	1072 KB	Output is correct
23	Correct	957 ms	872 KB	Output is correct
24	Correct	941 ms	1144 KB	Output is correct
25	Correct	7 ms	344 KB	Output is correct
26	Correct	11 ms	344 KB	Output is correct
27	Correct	27 ms	596 KB	Output is correct
28	Correct	21 ms	344 KB	Output is correct
29	Correct	19 ms	344 KB	Output is correct
30	Correct	212 ms	344 KB	Output is correct
31	Correct	220 ms	428 KB	Output is correct
32	Correct	201 ms	600 KB	Output is correct
33	Correct	326 ms	600 KB	Output is correct
34	Correct	311 ms	344 KB	Output is correct
35	Correct	337 ms	464 KB	Output is correct
36	Correct	944 ms	968 KB	Output is correct
37	Correct	905 ms	1020 KB	Output is correct
38	Correct	901 ms	964 KB	Output is correct
39	Correct	981 ms	960 KB	Output is correct
40	Correct	912 ms	1072 KB	Output is correct
41	Correct	851 ms	680 KB	Output is correct
42	Correct	849 ms	720 KB	Output is correct
43	Correct	862 ms	1216 KB	Output is correct
44	Correct	910 ms	1160 KB	Output is correct
45	Correct	9 ms	344 KB	Output is correct
46	Correct	7 ms	344 KB	Output is correct
47	Correct	27 ms	344 KB	Output is correct
48	Correct	16 ms	344 KB	Output is correct
49	Correct	23 ms	344 KB	Output is correct
50	Correct	197 ms	600 KB	Output is correct
51	Correct	215 ms	688 KB	Output is correct
52	Correct	185 ms	344 KB	Output is correct
53	Correct	325 ms	344 KB	Output is correct
54	Correct	295 ms	464 KB	Output is correct
55	Correct	332 ms	468 KB	Output is correct
56	Correct	909 ms	704 KB	Output is correct
57	Correct	961 ms	928 KB	Output is correct
58	Correct	955 ms	1020 KB	Output is correct
59	Correct	908 ms	928 KB	Output is correct
60	Correct	855 ms	1376 KB	Output is correct
61	Correct	895 ms	856 KB	Output is correct
62	Correct	888 ms	576 KB	Output is correct
63	Correct	867 ms	1160 KB	Output is correct
64	Correct	951 ms	1204 KB	Output is correct

Subtask #4

0.0 / 60.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	9 ms	344 KB	Output is correct
2	Correct	23 ms	344 KB	Output is correct
3	Partially correct	143 ms	700 KB	Output is partially correct
4	Partially correct	387 ms	724 KB	Output is partially correct
5	Partially correct	974 ms	988 KB	Output is partially correct
6	Correct	7 ms	344 KB	Output is correct
7	Correct	22 ms	344 KB	Output is correct
8	Partially correct	157 ms	448 KB	Output is partially correct
9	Partially correct	359 ms	444 KB	Output is partially correct
10	Partially correct	973 ms	952 KB	Output is partially correct
11	Partially correct	974 ms	880 KB	Output is partially correct
12	Partially correct	993 ms	992 KB	Output is partially correct
13	Partially correct	966 ms	612 KB	Output is partially correct
14	Correct	8 ms	344 KB	Output is correct
15	Correct	11 ms	344 KB	Output is correct
16	Incorrect	5 ms	596 KB	Incorrect
17	Halted	0 ms	0 KB	-