oj.uz

Submission #242643

# Submission time Handle Problem Language Result Execution time Memory
242643 2020-06-28T13:15:11 Z ZwariowanyMarcin Meetings (JOI19_meetings) C++14
0 / 100
 69 ms 640 KB 
#include "meetings.h"
#include <bits/stdc++.h>
#define ll long long
#define ld long double
#define pb push_back
#define mp make_pair
#define ss(x) (int) x.size()
#define fi first
#define se second
#define cat(x) cerr << #x << " = " << x << endl
#define rep(i, j, n) for (int i = j; i <= n; ++i)
#define per(i, j, n) for (int i = n; j <= i; --i)
#define all(x) x.begin(), x.end()
 
using namespace std;

const int N = 2100;
/*
int Query(int x, int y, int z) {
	printf ("ask %d %d %d\n", x, y, z);
	int d;
	cin >> d;
	return d;
}

void Bridge(int x, int y) {
	printf ("tree %d %d\n", x, y);
}*/

vector <int> g[N];

void rek(vector <int> x, int root) {
	if (ss(x) == 1) return;
	int y = x[rand() % ss(x)];
	while (y == root)
		y = x[rand() % ss(x)];
	for (auto it : x)
		g[it].clear();
	vector <int> path;
	for (auto it : x) {
		if (it == y || it == root) continue;
		int z = Query(root, y, it);
		if (it == z) path.pb(it);
		g[z].pb(it);
	}
	g[root].pb(root);
	g[y].pb(y);
	sort(all(path), [&](int a, int b) {
		int c = Query(root, a, b);
		if (c == a) return 1;
		else return 0;
	});
	// 1. 
	int First = (path.empty() ? y : path[0]);
	Bridge(First, root);
	rep(i, 0, ss(path) - 1) 
		Bridge(path[i], (i + 1 < ss(path) ? path[i + 1] : y));
	for (auto it : x)
		if (!g[it].empty())
			rek(g[it], it);
}
	

void Solve(int n) {
	srand(2137);
	vector <int> v(n);
	iota(all(v), 0);
	int root = rand() % n;
	rek(v, root);
}

Subtask #1
0 / 7.0

# Verdict Execution time Memory Grader output
1 Incorrect 5 ms 384 KB Wrong Answer [3]
2 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 5 ms 384 KB Wrong Answer [3]
2 Halted 0 ms 0 KB -

Subtask #3
0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 5 ms 384 KB Wrong Answer [3]
2 Halted 0 ms 0 KB -

Subtask #4
0 / 71.0

# Verdict Execution time Memory Grader output
1 Incorrect 69 ms 640 KB Wrong Answer [3]
2 Halted 0 ms 0 KB -