Submission #1082439

#	Time	Username	Problem	Language	Result	Execution time	Memory
1082439		Halym2007	Longest Trip (IOI23_longesttrip)	C++17	0 / 100	202 ms	6992 KiB

longesttrip

#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
• Subtask 1: 0 / 5
• Subtask 2: 0 / 10
• Subtask 3: 0 / 25
• Subtask 4: 0 / 60