| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 1082347 | 2024-08-31T07:58:05 Z | Halym2007 | 가장 긴 여행 (IOI23_longesttrip) | C++17 | 0 ms | 0 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);
}
}
}
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
*/