Submission #164081

#	Time	Username	Problem	Language	Result	Execution time	Memory
164081		atoiz	Meetings (JOI19_meetings)	C++14	100 / 100	1387 ms	984 KiB

meetings

#include "meetings.h"
#include <vector>
#include <algorithm>
#include <iostream>
#include <cassert>

using namespace std;
int total = 0;

int findSubSize(int u, int p, vector<vector<int>> &G, vector<int> &subSize, vector<bool> &dead)
{
	subSize[u] = 1;
	for (int v : G[u]) {
		if (v == p || dead[v]) continue;
		subSize[u] += findSubSize(v, u, G, subSize, dead);
	}
	return subSize[u];
}

int findCentroid(int u, int p, vector<vector<int>> &G, int treeSize, vector<int> &subSize, vector<bool> &dead)
{
	// cerr << u << ' ' << p << ' ' << treeSize << endl;
	bool isCentroid = 1;
	for (int v : G[u]) {
		if (v == p || dead[v]) continue;
		if (subSize[v] > treeSize / 2) isCentroid = 0;
	}
	if (treeSize - subSize[u] > treeSize / 2) isCentroid = 0;
	if (isCentroid) return u;

	for (int v : G[u]) {
		if (v == p || dead[v]) continue;
		int cand = findCentroid(v, u, G, treeSize, subSize, dead);
		if (cand) return cand;
	}
	return 0;
}

void addBetween(int u, int v, int w, vector<vector<int>> &G)
{
	*find(G[u].begin(), G[u].end(), v) = w;
	*find(G[v].begin(), G[v].end(), u) = w;
	G[w] = {u, v};
}


void addVertex(int nxt, vector<vector<int>> &G, vector<bool> &found, vector<bool> &dead, vector<int> &subSize)
{
	int N = (int) G.size();
	fill(dead.begin(), dead.end(), 0);

	int root = 0;
	while (!found[nxt]) {
		int curSize = findSubSize(root, -1, G, subSize, dead);
		int centroid = findCentroid(root, -1, G, curSize, subSize, dead);
		if (curSize == 1) {
			G[centroid].push_back(nxt);
			G[nxt].push_back(centroid);
			found[nxt] = 1;
			return;
		}

		findSubSize(centroid, -1, G, subSize, dead);

		vector<int> cands;
		for (int v : G[centroid]) {
			if (!dead[v]) cands.push_back(v);
		}
		sort(cands.begin(), cands.end(), [&](int u, int v) { return subSize[u] > subSize[v]; });

		for (int candRoot : cands) {
			int mid = Query(centroid, candRoot, nxt); // guaranteed all arguments are distinct
			if (mid == centroid) {
				continue;
			} else if (mid == candRoot) {
				root = candRoot, dead[centroid] = 1;
				break;
			} else if (mid == nxt) {
				addBetween(centroid, candRoot, nxt, G);
				found[nxt] = 1;
				return;
			} else {
				addBetween(centroid, candRoot, mid, G);
				G[mid].push_back(nxt);
				G[nxt].push_back(mid);
				found[mid] = found[nxt] = 1;
				return;
			}
		}

		if (!dead[centroid]) {
			G[centroid].push_back(nxt);
			G[nxt].push_back(centroid);
			found[nxt] = 1;
			return;
		}
	}
}

void Solve(int N)
{
	vector<vector<int>> G(N);
	G[1].push_back(0);
	G[0].push_back(1);

	vector<bool> found(N, 0);
	found[1] = found[0] = 1;

	vector<int> subSize(N);
	vector<bool> dead(N);
	for (int nxt = 2; nxt < N; ++nxt) {
		if (!found[nxt]) {
			addVertex(nxt, G, found, dead, subSize);
		}
	}

	// std::cerr << "total " << total << std::endl;
	for (int u = 0; u < N; ++u) {
		for (int v : G[u]) {
			if (u < v) {
				Bridge(u, v);
			}
		}
	}

}

Compilation message (stderr)

meetings.cpp: In function 'void addVertex(int, std::vector<std::vector<int> >&, std::vector<bool>&, std::vector<bool>&, std::vector<int>&)':
meetings.cpp:49:6: warning: unused variable 'N' [-Wunused-variable]
  int N = (int) G.size();
      ^

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