Submission #203625

#	Time	Username	Problem	Language	Result	Execution time	Memory
203625		ics0503	Meetings (JOI19_meetings)	C++17	100 / 100	832 ms	14968 KiB

meetings

#include "meetings.h"
#include<vector>
#include<algorithm>
using namespace std;
int is_in[2121], P[2121], W[2121][2121];
struct xy { int x, y; };
bool sort_y(xy a, xy b) { if (a.y != b.y)return a.y > b.y; return a.x < b.x; }
vector<xy>edge[2121];
int C[2121], nown, mx, cent;
void dfs(int w, int bef) {
	C[w] = 1;
	int flag = 1;
	for (xy E : edge[w]) if (!E.y && E.x != bef) {
		dfs(E.x, w);
		if (C[E.x] > nown / 2)flag = 0;
		C[w] += C[E.x];
	}
	if (nown - C[w] > nown / 2)flag = 0;
	if (flag)cent = w;
}
void connect(int p, int c, int who) {
	int x = Query(p, c, who);
	if (x == p)P[c] = P[who] = p;
	else if (x == c)P[c] = p, P[who] = c;
	else if (x == who)P[c] = who, P[who] = p;
	else is_in[x] = 1, P[c] = P[who] = x, P[x] = p;
}
void disconnect(int a, int b) { edge[a][W[a][b]].y = edge[b][W[b][a]].y = 1; }
void Solve(int N) {
	connect(0, 1, 2);
	is_in[0] = is_in[1] = is_in[2] = 1;
	for (int now = 3; now < N; now++) {
		if (is_in[now])continue;
		nown = 1;
		for (int i = 1; i < N; i++) {
			if (is_in[i]) {
				W[P[i]][i] = edge[P[i]].size(); edge[P[i]].push_back({ i,0 });
				W[i][P[i]] = edge[i].size(); edge[i].push_back({ P[i],0 });
				nown++;
			}
		}
		int root = 0;
		while (1) {
			mx = cent = 0;
			dfs(root, -1);
			if (C[root] == 1) {
				P[now] = root; break;
			}
			vector<xy>L; int cnt = 0;
			for (xy E : edge[cent]) if (!E.y) {
				L.push_back({ E.x,(C[E.x] < C[cent] ? C[E.x] : nown - C[cent]) });
			}
			sort(L.begin(), L.end(), sort_y);
			if (L.size() == 1) {
				int who = L[0].x, p, c;
				if (P[cent] == who) p = who, c = cent;
				else p = cent, c = who;
				connect(p, c, now);
				break;
			}
			else {
				int ck = 0; root = cent;
				for (int i = 1; i < L.size(); i += 2) {
					int a = L[i - 1].x, b = L[i].x;
					int x = Query(a, b, now);
					if (x == cent) disconnect(a, cent), disconnect(b, cent), nown -= L[i - 1].y, nown -= L[i].y;
					else {
						if (x == a)      disconnect(a, cent), root = a, nown = L[i - 1].y;
						else if (x == b) disconnect(b, cent), root = b, nown = L[i].y;
						else {
							int y = Query(a, x, cent); ck = 1;
							if (y == x) {
								if (P[a] == cent) { P[a] = P[now] = x; P[x] = cent; is_in[x] = 1; }
								else              { P[cent] = P[now] = x; P[x] = a; is_in[x] = 1; }
							}
							else {
								if (P[b] == cent) { P[b] = P[now] = x; P[x] = cent; is_in[x] = 1; }
								else              { P[cent] = P[now] = x; P[x] = b; is_in[x] = 1; }
							}
						}
						break;
					}
				}
				if (ck) break;
			}
		}
		is_in[now] = 1;
		for (int i = 0; i < N; i++)edge[i].clear();
	}
	for (int i = 1; i < N; i++) {
		if(i<P[i]) Bridge(i, P[i]);
		else Bridge(P[i], i);
	}
}

Compilation message (stderr)

meetings.cpp: In function 'void Solve(int)':
meetings.cpp:63:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 1; i < L.size(); i += 2) {
                     ~~^~~~~~~~~~
meetings.cpp:49:21: warning: unused variable 'cnt' [-Wunused-variable]
    vector<xy>L; int cnt = 0;
                     ^~~

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