Submission #536092

#	Time	Username	Problem	Language	Result	Execution time	Memory
536092		blue	Meetings (JOI19_meetings)	C++17	100 / 100	904 ms	1164 KiB

meetings

#include "meetings.h"
#include <iostream>
#include <vector>
#include <algorithm>
#include <set>
#include <random>
using namespace std;

using vi = vector<int>;
#define sz(x) int(x.size())

const int mx = 2'000;
int N;

set<int> edge[mx];

void cut(int u, int v)
{
	edge[u].erase(v);
	edge[v].erase(u);
}

void join(int u, int v)
{
	edge[u].insert(v);
	edge[v].insert(u);
}


vi subtree;
vi depth;
int goodct;

void dfs(int u, int p, vi& good)
{
	goodct++;
	for(int v : edge[u])
	{
		if(v == p) continue;
		if(!good[v]) continue;

		depth[v] = depth[u] + 1;
		dfs(v, u, good);
		subtree[u] += subtree[v];
	}
}

vi childlist;

vi added(mx, 0);



void computelist(int u, int p, vi& newgood, vi& oldgood)
{
	newgood[u] = 1;
	for(int v : edge[u])
	{
		if(v == p) continue;
		if(!oldgood[v]) continue;

		computelist(v, u, newgood, oldgood);
	}
}



void Locate(vi good, int X)
{
	// cerr << "Locate " << X << "  ";
	// for(int f = 0; f < N; f++) cerr << good[f] << ' ';
	// 	cerr << "\n";
	subtree = vi(N, 1);
	depth = vi(N, 1);
	int rt = 0;
	while(!good[rt]) rt++;

	goodct = 0;

	dfs(rt, rt, good);

	int cent = -1;
	for(int i = 0; i < N; i++)
	{
		if(!good[i]) continue;

		if(2*subtree[i] < goodct) continue;

		if(cent == -1) cent = i;
		else if(depth[i] > depth[cent]) cent = i;
	}

	childlist.clear();

	for(int x : edge[cent])
		if(good[x])
			childlist.push_back(x);

	sort(childlist.begin(), childlist.end(), [] (int p, int q)
	{
		return subtree[p] > subtree[q];
	});

	int desc = -1;


	for(int h = 0; h+1 < sz(childlist); h++)
	{
		int A = childlist[h], B = childlist[h+1];

		int Q = Query(A, B, X);

		if(Q == A)
		{
			desc = A;
			break;
		}
		else if(Q == B)
		{
			desc = B;
			break;
		}
		else if(Q == cent)
		{
			continue;
		}
		else if(Q == X)
		{
			int Q2 = Query(cent, X, A);
			if(Q2 == X)
			{
				cut(cent, A);
				join(cent, X);
				join(A, X);

				added[X] = 1;

				return;
			}
			else
			{
				cut(cent, B);
				join(cent, X);
				join(B, X);

				added[X] = 1;

				return;
			}
		}
		else
		{
			int Q2 = Query(cent, Q, A);
			if(Q2 == Q)
			{
				cut(cent, A);
				join(cent, Q);
				join(Q, A);
				join(Q, X);

				added[Q] = added[X] = 1;
			}
			else
			{
				cut(cent, B);
				join(cent, Q);
				join(Q, B);
				join(Q, X);

				added[Q] = added[X] = 1;
			}

			return;
		}
	}

	if(desc == -1)
	{
		if(sz(childlist) % 2 == 1)
		{
			int z = childlist.back();

			int Q = Query(cent, z, X);

			if(Q == cent)
			{
				join(cent, X);

				added[X] = 1;

				return;
			}
			else if(Q == z)
			{
				desc = z;
			}
			else if(Q == X)
			{
				cut(cent, z);
				join(cent, X);
				join(X, z);

				added[X] = 1;

				return;
			}
			else
			{
				cut(cent, z);
				join(cent, Q);
				join(Q, X);
				join(Q, z);

				added[X] = added[Q] = 1;

				return;
			}
		}
		else
		{
			join(cent, X);

			added[X] = 1;

			return;
		}
	}

	vi goodlist(N, 0);
	computelist(desc, cent, goodlist, good);


	// cerr << "desc = " << desc << '\n';

	Locate(goodlist, X);
}

void Solve(int N_) 
{
	N = N_;

	edge[0].insert(1);
	edge[1].insert(0);

	added[0] = added[1] = 1;

	vi addlist;
	for(int X = 2; X <= N-1; X++)
		addlist.push_back(X);

	// for(int k = 0; k < 1'000'000; k++)
	// {
	// 	int u = rand() % sz(addlist);
	// 	int v = rand() % sz(addlist);
	// 	swap(addlist[u], addlist[v]);
	// }

	for(int X : addlist)
	{
		if(added[X]) continue;
		// cerr << "original new\n";
		Locate(added, X);
	}

	for(int u = 0; u < N; u++)
		for(int v : edge[u])
			if(u < v)
				Bridge(u, v);
}

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