oj.uz

Submission #470457

# Submission time Handle Problem Language Result Execution time Memory
470457 2021-09-03T21:03:02 Z Namnamseo Meetings (JOI19_meetings) C++17
0 / 100
 73 ms 492 KB 
#include "meetings.h"
#include <algorithm>
#include <cassert>
#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; }
	assert(int(foots.size()) == n);
	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);
}

Subtask #1
0 / 7.0

# 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 328 KB Output is correct
4 Correct 0 ms 384 KB Output is correct
5 Correct 0 ms 328 KB Output is correct
6 Incorrect 0 ms 200 KB Wrong Answer [4]
7 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# 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 328 KB Output is correct
4 Correct 0 ms 384 KB Output is correct
5 Correct 0 ms 328 KB Output is correct
6 Incorrect 0 ms 200 KB Wrong Answer [4]
7 Halted 0 ms 0 KB -

Subtask #3
0 / 12.0

# 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 328 KB Output is correct
4 Correct 0 ms 384 KB Output is correct
5 Correct 0 ms 328 KB Output is correct
6 Incorrect 0 ms 200 KB Wrong Answer [4]
7 Halted 0 ms 0 KB -

Subtask #4
0 / 71.0

# Verdict Execution time Memory Grader output
1 Incorrect 73 ms 492 KB Wrong Answer [4]
2 Halted 0 ms 0 KB -