Submission #470455

# Submission time Handle Problem Language Result Execution time Memory
470455 2021-09-03T20:42:59 Z Namnamseo Meetings (JOI19_meetings) C++17
0 / 100
73 ms 456 KB
#include "meetings.h"
#include <algorithm>
#include <map>
#include <numeric>
#include <vector>
using namespace std;

void bridge(int a, int b) { if (a>b) swap(a, b); Bridge(a, b); }

void work_set(vector<int> &v) {
	if (v.size() == 1u) return;
	int a = v[0], b = v[1], n = v.size();
	map<int, vector<int>> roots;
	roots[a] = {a}; roots[b] = {b};
	for (int i=2; i<n; ++i) roots[Query(a, b, v[i])].push_back(v[i]);
	for (auto &tmp : roots) work_set(tmp.second);
	n = roots.size()-2u;
	vector<int> foots; foots.reserve(n);
	for (auto &tmp : roots) if (tmp.first != a && tmp.first != b) foots.push_back(tmp.first);
	if (foots.empty()) { bridge(a, b); return; }
	roots = move(decltype(roots)());
	sort(foots.begin(), foots.end(), [&](const int& x, const int& y) {
		return Query(x, y, a) == a;
	});
	bridge(a, foots[0]);
	for (int i=1; i<n; ++i) bridge(foots[i-1], foots[i]);
	bridge(foots[n-1], b);
}

void Solve(int N) {
	vector<int> v(N);
	iota(v.begin(), v.end(), 0);
	work_set(v);
}
# Verdict Execution time Memory Grader output
1 Correct 0 ms 328 KB Output is correct
2 Correct 0 ms 328 KB Output is correct
3 Correct 0 ms 200 KB Output is correct
4 Correct 0 ms 200 KB Output is correct
5 Correct 1 ms 200 KB Output is correct
6 Incorrect 0 ms 200 KB Wrong Answer [4]
7 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Correct 0 ms 328 KB Output is correct
2 Correct 0 ms 328 KB Output is correct
3 Correct 0 ms 200 KB Output is correct
4 Correct 0 ms 200 KB Output is correct
5 Correct 1 ms 200 KB Output is correct
6 Incorrect 0 ms 200 KB Wrong Answer [4]
7 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Correct 0 ms 328 KB Output is correct
2 Correct 0 ms 328 KB Output is correct
3 Correct 0 ms 200 KB Output is correct
4 Correct 0 ms 200 KB Output is correct
5 Correct 1 ms 200 KB Output is correct
6 Incorrect 0 ms 200 KB Wrong Answer [4]
7 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Incorrect 73 ms 456 KB Wrong Answer [4]
2 Halted 0 ms 0 KB -