oj.uz

답안 #1082350

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


*/

Subtask #0
0.0 / 0.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 4952 KB Output is correct
2 Correct 189 ms 5608 KB Output is correct

Subtask #1
0.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 8 ms 4952 KB Output is correct
2 Incorrect 22 ms 4952 KB Incorrect
3 Halted 0 ms 0 KB -

Subtask #2
0.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 4952 KB Output is correct
2 Incorrect 24 ms 4952 KB Incorrect
3 Halted 0 ms 0 KB -

Subtask #3
0.0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 9 ms 4952 KB Output is correct
2 Incorrect 28 ms 4952 KB Incorrect
3 Halted 0 ms 0 KB -

Subtask #4
0.0 / 60.0

# 결과 실행 시간 메모리 Grader output
1 Correct 7 ms 4952 KB Output is correct
2 Incorrect 23 ms 4952 KB Incorrect
3 Halted 0 ms 0 KB -