Submission #401062

#	Time	Username	Problem	Language	Result	Execution time	Memory
401062		saleh	Fun Tour (APIO20_fun)	C++17	26 / 100	15 ms	404 KiB

fun

#include "fun.h"

#include <bits/stdc++.h>


using namespace std;


const int MAXN = 500 + 3;




/*
int hoursRequired(int i, int j) {
	cout << i << ' ' << j << endl;
	cin >> i;
	return i;
}*/




int dis[MAXN], n;
bitset<MAXN> mark, mirk;
vector<int> g[MAXN];

int door(int v) {
	mirk.reset();
	memset(dis, 31, sizeof dis);
	dis[v] = 0;
	queue<int> q;
	q.push(v);
	while(!q.empty()) {
		int x = q.front();
		q.pop();
		if (mirk[x]) continue;
		mirk[x] = true;
		for (auto i : g[x]) if (!mark[i] && dis[i] > dis[x] + 1) {
			dis[i] = dis[x] + 1;
			q.push(i);
		}
	}
	for (int i = 0; i < n; i++) if (mark[i]) dis[i] = -1;
	return max_element(dis, dis + n) - dis;
}


vector<int> createFunTour(int N, int q) {
	n = N;
	if (n >= MAXN) return {};
	vector<int> v;
  	for (int i = 0; i < n; i++) for (int j = i + 1; j < n; j++) if (hoursRequired(i, j) == 1) g[i].push_back(j), g[j].push_back(i);
  	int x = door(0);
  	for (int i = 0; i < n; i++) {
  		int y = door(x);
  		mark[x] = true;
  		v.push_back(x);
  		x = y;
  	}
	return v;
}

/*
int main() {
	for (auto i : createFunTour(7, 10)) cout << i << endl;
	return 0;
}*/

• Subtask 1: 10 / 10
• Subtask 2: 16 / 16
• Subtask 3: 0 / 21
• Subtask 4: 0 / 19
• Subtask 5: 0 / 34