oj.uz

Submission #1069714

# Submission time Handle Problem Language Result Execution time Memory
1069714 2024-08-22T08:29:56 Z UmairAhmadMirza Longest Trip (IOI23_longesttrip) C++17
15 / 100
 835 ms 856 KB 
#include <bits/stdc++.h>
using namespace std;

bool are_connected(vector<int> A, vector<int> B);

int const MAXN=260;
bool con[MAXN][MAXN];
vector<int> path,longest;
bool vis[MAXN];
int nn;
void dfs(int node){
	path.push_back(node);
	if(path.size()>longest.size())
		longest=path;
	vis[node]=1;
	for(int i=0;i<nn;i++)
		if(vis[i]==0 && con[node][i])
			dfs(i);
	path.pop_back();
}
vector<int> longest_trip(int n, int D){
	longest.clear();
	nn=n;
	vector<int> a,b;
	for(int i=0;i<n;i++){
		a.push_back(i);
		for(int j=i+1;j<n;j++){
			b.push_back(j);
			con[i][j]=con[j][i]=are_connected(a,b);
			b.pop_back();
		}
		a.pop_back();
	}
	if(D>1){
		path.clear();
		for (int i = 0; i < n; ++i)
			path.push_back(i);
		bool bl=0;
		for(int i=0;i<n-1;i++)
			if(con[path[i]][path[i+1]]==0){
				if(i==n-2)
					rotate(path.rbegin(), path.rbegin() + 1, path.rend());
				else
					swap(path[i+1],path[i+2]);
			}
		return path;
	}
	// for (int i = 0; i < n; ++i)
	// {
	// 	path.clear();
	// 	for(int j=0;j<n;j++)
	// 		vis[j]=0;
	// 	dfs(i);
	// }
	return longest;
}

Compilation message

longesttrip.cpp: In function 'std::vector<int> longest_trip(int, int)':
longesttrip.cpp:38:8: warning: unused variable 'bl' [-Wunused-variable]
   38 |   bool bl=0;
      |        ^~

Subtask #0
0.0 / 0.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 344 KB Incorrect
2 Halted 0 ms 0 KB -

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 344 KB Output is correct
2 Correct 31 ms 344 KB Output is correct
3 Correct 150 ms 344 KB Output is correct
4 Correct 355 ms 344 KB Output is correct
5 Correct 829 ms 480 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 344 KB Output is correct
2 Correct 19 ms 344 KB Output is correct
3 Correct 162 ms 344 KB Output is correct
4 Correct 394 ms 856 KB Output is correct
5 Correct 704 ms 484 KB Output is correct
6 Correct 7 ms 344 KB Output is correct
7 Correct 23 ms 344 KB Output is correct
8 Correct 155 ms 344 KB Output is correct
9 Correct 308 ms 344 KB Output is correct
10 Correct 780 ms 476 KB Output is correct
11 Correct 791 ms 480 KB Output is correct
12 Correct 731 ms 480 KB Output is correct
13 Correct 835 ms 600 KB Output is correct

Subtask #3
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 340 KB Incorrect
2 Halted 0 ms 0 KB -

Subtask #4
0.0 / 60.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 344 KB Incorrect
2 Halted 0 ms 0 KB -