Submission #373750

#	Time	Username	Problem	Language	Result	Execution time	Memory
373750		luciocf	Meetings (JOI19_meetings)	C++14	0 / 100	327 ms	262148 KiB

meetings

#include <bits/stdc++.h>
#include "meetings.h"

#define ff first
#define ss second

using namespace std;

const int maxn = 2010;

int n;

int sz[maxn];
bool mark[maxn];

vector<int> grafo[maxn];

void dfs(int u, int p)
{
	sz[u] = 1;

	for (auto v: grafo[u])
	{
		if (v == p || mark[v]) continue;

		dfs(v, u);
		sz[u] += sz[v];
	}
}

int centroid(int u, int p, int S)
{
	for (auto v: grafo[u])
		if (v != p && !mark[v] && sz[v] > S/2)
			return centroid(v, u, S);

	return u;
}

void add_between(int a, int b, int c)
{
	grafo[a].push_back(c);
	grafo[c].push_back(a);

	for (int i = 0; i < grafo[a].size(); i++)
	{
		int v = grafo[a][i];

		if (v == b)
		{
			swap(grafo[a][i], grafo[a].back());
			grafo[a].pop_back();
			break;
		}
	}

	grafo[c].push_back(b);
	grafo[b].push_back(c);
}

void Solve(int N)
{
	n = N;

	for (int i = 2; i <= n; i++)
	{
		memset(mark, 0, sizeof mark);

		int at = 1;

		while (true)
		{
			dfs(at, 0);
			int c = centroid(at, 0, sz[at]);
			mark[c] = 1;

			bool found = 0;
			bool keep = 0;

			for (auto v: grafo[c])
			{
				if (mark[v]) continue;

				int k = Query(c-1, v-1, i-1)+1;
				if (k == c) continue;

				if (k == i)
				{
					add_between(c, v, i);
					found = 1;
					break;
				}

				keep = 1;
				at = v;
			}

			if (found) break;

			if (!keep)
			{
				grafo[c].push_back(i);
				grafo[i].push_back(c);
				break;
			}
		}
	}

	set<pair<int, int>> st;

	for (int i = 1; i <= n; i++)
		for (auto j: grafo[i])
			st.insert({min(i, j), max(i, j)});

	for (auto pp: st)
		Bridge(pp.ff-1, pp.ss-1);
}

Compilation message (stderr)

meetings.cpp: In function 'void add_between(int, int, int)':
meetings.cpp:45:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   45 |  for (int i = 0; i < grafo[a].size(); i++)
      |                  ~~^~~~~~~~~~~~~~~~~

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