oj.uz

Submission #962511

# Submission time Handle Problem Language Result Execution time Memory
962511 2024-04-13T17:53:17 Z alex_2008 Longest Trip (IOI23_longesttrip) C++17
15 / 100
 794 ms 1708 KB 
#include "longesttrip.h"
#include <vector>
#include <iostream>
#include <cmath>
#include <algorithm>
using namespace std;
const int N = 5e2 + 10;
bool used[N];
vector <int> G[N];
vector <int> cur;
bool solved = false;
int f(int v) {
	int cnt = 0;
	for (auto it : G[v]) {
		if (!used[it]) ++cnt;
	}
	return cnt;
}
void dfs(int v, int n) {
	if (solved) return;
	used[v] = true;
	cur.push_back(v);
	if ((int)cur.size() == n) {
		solved = true;
		return;
	}
	int mn_deg = 1000, w = -1;
	for (auto it : G[v]) {
		if (!used[it]) {
			int q = f(it);
			if (q < mn_deg) {
				mn_deg = q;
				w = it;
			}
		}
	}
	if (w != -1) {
		dfs(w, n);
	}
}
bool find_edge(int a, int b) {
	return are_connected({ a }, { b });
}
vector <int> longest_trip(int n, int d) {
	if (d == 3) {
		vector <int> w(n);
		for (int i = 0; i < n; i++) {
			w[i] = i;
		}
		return w;
	}
	if (d == 2) {
		solved = false;
		for (int i = 0; i < n; i++) {
			G[i].clear();
		}
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < i; j++) {
				vector <int> v1, v2;
				v1.push_back(i);
				v2.push_back(j);
				if (are_connected(v1, v2)) {
					G[i].push_back(j);
					G[j].push_back(i);
				}
			}
		}
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < n; j++) {
				used[j] = false;
			}
			dfs(i, n);
			vector <int> ret = cur;
			cur.clear();
			if (solved) {
				return ret;
			}
		}
	}
	vector <int> p1, p2;
	p1.push_back(0);
	p2.push_back(1);
	for (int i = 2; i < n; i++) {
		if (find_edge(p1.back(), i)) {
			p1.push_back(i);
		}
		else if (find_edge(p2.back(), i)) {
			p2.push_back(i);
		}
		else {
			while (!p2.empty()) {
				p1.push_back(p2.back()); 
				p2.pop_back();
			}
			p2.push_back(i);
		}
	}
	if (find_edge(p1[0], p2[0])) {
		vector <int> ans;
		reverse(p1.begin(), p1.end());
		for (auto& it : p1) {
			ans.push_back(it);
		}
		for (auto& it : p2) {
			ans.push_back(it);
		}
		return ans;
	}
	if (find_edge(p1[0], p2.back())) {
		vector <int> ans;
		reverse(p1.begin(), p1.end());
		reverse(p2.begin(), p2.end());
		for (auto& it : p1) {
			ans.push_back(it);
		}
		for (auto& it : p2) {
			ans.push_back(it);
		}
		return ans;
	}
	if (find_edge(p1.back(), p2[0])) {
		vector <int> ans;
		for (auto& it : p1) {
			ans.push_back(it);
		}
		for (auto& it : p2) {
			ans.push_back(it);
		}
		return ans;
	}
	if (find_edge(p1.back(), p2.back())) {
		vector <int> ans;
		reverse(p2.begin(), p2.end());
		for (auto& it : p1) {
			ans.push_back(it);
		}
		for (auto& it : p2) {
			ans.push_back(it);
		}
		return ans;
	}
	if (!are_connected(p1, p2)) {
		if ((int)p1.size() > (int)p2.size()) {
			return p1;
		}
		return p2;
	}
	int l = 0, r = (int)p1.size() - 1, ans = -1;
	while (l <= r) {
		int mid = (l + r) / 2;
		vector <int> w;
		for (int i = mid; i < (int)p1.size(); i++) {
			w.push_back(p1[i]);
		}
		if (are_connected(w, p2)) {
			ans = mid;
			l = mid + 1;
		}
		else r = mid - 1;
	}
	int vert1 = ans;
	l = 0, r = (int)p2.size() - 1, ans = -1;
	while (l <= r) {
		int mid = (l + r) / 2;
		vector <int> w;
		for (int i = mid; i < (int)p2.size(); i++) {
			w.push_back(p2[i]);
		}
		if (are_connected({ vert1 }, w)) {
			ans = mid;
			l = mid + 1;
		}
		else r = mid - 1;
	}
	int vert2 = ans;
	vector <int> final_ans;
	for (int i = vert1 + 1; i < (int)p1.size(); i++) {
		final_ans.push_back(p1[i]);
	}
	for (int i = 0; i <= vert1; i++) {
		final_ans.push_back(p1[i]);
	}
	for (int i = vert2; i < (int)p2.size(); i++) {
		final_ans.push_back(p2[i]);
	}
	for (int i = 0; i < vert2; i++) {
		final_ans.push_back(p2[i]);
	}
	return final_ans;
}

Subtask #0
0.0 / 0.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 1 ms 344 KB Output is correct

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 344 KB Output is correct
2 Correct 1 ms 344 KB Output is correct
3 Correct 1 ms 596 KB Output is correct
4 Correct 1 ms 344 KB Output is correct
5 Correct 0 ms 344 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 344 KB Output is correct
2 Correct 22 ms 344 KB Output is correct
3 Correct 138 ms 712 KB Output is correct
4 Correct 346 ms 1148 KB Output is correct
5 Correct 766 ms 1672 KB Output is correct
6 Correct 8 ms 344 KB Output is correct
7 Correct 23 ms 344 KB Output is correct
8 Correct 150 ms 600 KB Output is correct
9 Correct 294 ms 860 KB Output is correct
10 Correct 771 ms 1672 KB Output is correct
11 Correct 783 ms 1668 KB Output is correct
12 Correct 794 ms 1472 KB Output is correct
13 Correct 784 ms 1708 KB Output is correct

Subtask #3
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 344 KB Output is correct
2 Correct 5 ms 344 KB Output is correct
3 Correct 4 ms 344 KB Output is correct
4 Correct 4 ms 344 KB Output is correct
5 Correct 5 ms 500 KB Output is correct
6 Correct 10 ms 344 KB Output is correct
7 Correct 6 ms 344 KB Output is correct
8 Correct 5 ms 344 KB Output is correct
9 Correct 5 ms 344 KB Output is correct
10 Correct 6 ms 344 KB Output is correct
11 Correct 5 ms 344 KB Output is correct
12 Correct 5 ms 344 KB Output is correct
13 Correct 4 ms 344 KB Output is correct
14 Correct 12 ms 340 KB Output is correct
15 Correct 12 ms 344 KB Output is correct
16 Incorrect 1 ms 344 KB Incorrect
17 Halted 0 ms 0 KB -

Subtask #4
0.0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 344 KB Output is correct
2 Correct 7 ms 344 KB Output is correct
3 Correct 6 ms 340 KB Output is correct
4 Correct 5 ms 344 KB Output is correct
5 Correct 5 ms 600 KB Output is correct
6 Correct 7 ms 344 KB Output is correct
7 Correct 5 ms 344 KB Output is correct
8 Correct 4 ms 344 KB Output is correct
9 Correct 5 ms 344 KB Output is correct
10 Correct 5 ms 600 KB Output is correct
11 Correct 5 ms 600 KB Output is correct
12 Correct 4 ms 344 KB Output is correct
13 Correct 5 ms 344 KB Output is correct
14 Correct 14 ms 344 KB Output is correct
15 Correct 11 ms 344 KB Output is correct
16 Incorrect 1 ms 344 KB Incorrect
17 Halted 0 ms 0 KB -