Submission #1170926

#	Time	Username	Problem	Language	Result	Execution time	Memory
1170926		miniob	Meetings (JOI19_meetings)	C++20	100 / 100	1159 ms	1112 KiB

meetings

#include <bits/stdc++.h>
#include "meetings.h"
using namespace std;


int gdzie[2007];
set<int> mozliwe[2007];
int n, ile = 0;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

vector<int> kolejnoc_sciezki(vector<int> cojest, int korz)
{
	if (cojest.size() == 0)
	{
		return {};
	}
	else if (cojest.size() == 1)
	{
		return cojest;
	}
	else if (cojest.size() == 2)
	{
		int odp = Query(korz, cojest[0], cojest[1]);
		if (odp == cojest[0])
		{
			return cojest;
		}
		else
		{
			return { cojest[1], cojest[0] };
		}
	}
	else
	{
		int sr = rng() % cojest.size();
		vector<int> wczesniej;
		vector<int> pozniej;
		for (int i = 0; i < cojest.size(); i++)
		{
			if (i != sr)
			{
				int odp = Query(korz, cojest[sr], cojest[i]);
				if (odp == cojest[sr])
				{
					pozniej.push_back(cojest[i]);
				}
				else
				{
					wczesniej.push_back(cojest[i]);
				}
			}
		}
		wczesniej = kolejnoc_sciezki(wczesniej, korz);
		pozniej = kolejnoc_sciezki(pozniej, korz);
		vector<int> odp = wczesniej;
		odp.push_back(cojest[sr]);
		for (auto x : pozniej)
		{
			odp.push_back(x);
		}
		return odp;
	}
}

void roziwaz(int korz)
{
	if (ile >= n - 1)
	{
		return;
	}
	//cerr << "korzen " << korz << " mozliwe " << mozliwe[korz].size() << endl;
	if (mozliwe[korz].size() == 0)
	{
		return;
	}
	auto it = mozliwe[korz].begin();
	//cerr << "ok" << endl;
	int iledop = rng() % mozliwe[korz].size();
	//cerr << iledop << endl;
	advance(it, iledop);
	int doczego = *it;
	//cerr << "dokad " << doczego << endl;
	vector<int> nasc;
	vector<pair<int, int>> do_usu;
	vector<pair<int, int>> do_dodania;
	for (auto x : mozliwe[korz])
	{
		if (x != doczego)
		{
			int odp = Query(korz, doczego, x);
			//cerr << korz << " " << doczego << " " << x << " " << odp << endl;
			if (odp == x)
			{
				nasc.push_back(x);
				do_usu.push_back({ x, korz });
			}
			else
			{
				do_usu.push_back({ x, gdzie[x] });
				do_dodania.push_back({ x, odp });
			}
		}
		else
		{
			do_usu.push_back({ x, gdzie[x] });
		}
	}
	for (auto x : do_usu)
	{
		if (gdzie[x.first] != -1)
		{
			mozliwe[x.second].erase(x.first);
			gdzie[x.first] = -1;
		}
	}
	for (auto x : do_dodania)
	{
		mozliwe[x.second].insert(x.first);
		gdzie[x.first] = x.second;
	}
	vector<int> sciezka;
	sciezka.push_back(korz);
	vector<int> temp = kolejnoc_sciezki(nasc, korz);
	for (auto x : temp)
	{
		sciezka.push_back(x);
	}
	sciezka.push_back(doczego);
	for (int i = 0; i < sciezka.size() - 1; i++)
	{
		//cerr << sciezka[i] << " " << sciezka[i + 1] << endl;
		if (sciezka[i] > sciezka[i + 1])
		{
			Bridge(sciezka[i + 1], sciezka[i]);
		}
		else
		{
			Bridge(sciezka[i], sciezka[i + 1]);
		}
		ile++;
	}
	for (auto x : sciezka)
	{
		roziwaz(x);
	}
	return;
}

void Solve(int N)
{
	n = N;
	int startowy = rng() % n;
	for (int i = 0; i < n; i++)
	{
		if (i != startowy)
		{
			mozliwe[startowy].insert(i);
			gdzie[i] = startowy;
		}
	}
	roziwaz(startowy);
}

• Subtask 1: 7 / 7
• Subtask 2: 10 / 10
• Subtask 3: 12 / 12
• Subtask 4: 71 / 71