oj.uz

Submission #1082439

# Submission time Handle Problem Language Result Execution time Memory
1082439 2024-08-31T10:52:05 Z Halym2007 Longest Trip (IOI23_longesttrip) C++17
0 / 100
 202 ms 6992 KB 
#include <bits/stdc++.h>
#include "longesttrip.h"
using namespace std;
#define ll long long
#define sz size()
#define ff first
#define ss second
#define pb push_back
#define pii pair <int, int>
const int N = 2e5 + 5;



//bool are_connected (vector <int> A, vector <int> B) {
//	return true;
//}

pii jog;
vector <int> v[N];
int n, vis[N][2];
vector <int> ret, belle;

void dfs (int x, int type, int val) {
	vis[x][type] = 1;
	if (type == 1) {
		ret.pb (x);
	}
	if (jog.ff < val) {
		jog = {val, x};
		belle = ret;
	}
	
	for (int i : v[x]) {
		if (vis[i][type]) continue;
		dfs (i, type, val + 1);
	}
	ret.pop_back();
	
}

vector<int> longest_trip(int N, int D) {
	int n = N;
	for (int i = 0; i < n; ++i) {
		for (int j = i + 1; j < n; ++j) {
			if (are_connected({i}, {j})) {
				v[i].pb (j);
				v[j].pb (i);
			}
		}
	}    
	for (int i = 0; i < n; ++i) {
		if (vis[i][0]) continue;
		dfs (0, 0, 1);
	}
	int bel = jog.ss;
	jog = {0, 0};
	ret.clear();
	dfs (bel, 1, 1);
	for (int i = 0; i < n; ++i) {
		v[i].clear();
		for (int j = 0; j < 2; ++j) {
			vis[i][j] = 0;
		}	
	}
    return belle;
}


/*
2
5 1
1
1 1
0 0 1
0 0 0 1
4 1
1
0 0
0 0 1
answer : 
5
1 0 2 3 4
4
2
0 1
3
4


*/

Subtask #0
0.0 / 0.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 6488 KB Output is correct
2 Correct 202 ms 6992 KB Output is correct

Subtask #1
0.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 6488 KB Output is correct
2 Incorrect 27 ms 6488 KB Incorrect
3 Halted 0 ms 0 KB -

Subtask #2
0.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 6488 KB Output is correct
2 Incorrect 33 ms 6488 KB Incorrect
3 Halted 0 ms 0 KB -

Subtask #3
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 6488 KB Output is correct
2 Incorrect 30 ms 6488 KB Incorrect
3 Halted 0 ms 0 KB -

Subtask #4
0.0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 6488 KB Output is correct
2 Incorrect 24 ms 6488 KB Incorrect
3 Halted 0 ms 0 KB -