Submission #207010

#	Time	Username	Problem	Language	Result	Execution time	Memory
207010		E869120	Meetings (JOI19_meetings)	C++14	100 / 100	1174 ms	3452 KiB

meetings

#include "meetings.h"
#include <vector>
#include <map>
#include <ctime>
#include <iostream>
#include <algorithm>
using namespace std;

// 同じコードを提出して，https://oj.uz/submission/206974 では 100 点取れているんですけど，
// ひどい仕打ちをやめてくれ！
// おい，なめてんのか，grader の Query 関数は LCA で O(log N) で実装できるのに，なんで実装サボってんだ！！！！！！

vector<int> G[2009];
vector<int> I, J1, J2;
int ret1, ret2, ret3, ret4, allret;
bool passed[2009];
bool forced[2009];
map<pair<int, int>, int> Map[2009];

int Ask(int u, int v, int w) {
	int x[3] = { u, v, w };
	sort(x, x + 3);
	if (Map[x[0]][make_pair(x[1], x[2])] >= 1) return Map[x[0]][make_pair(x[1], x[2])] - 1;
	int Z = Query(x[0], x[1], x[2]);
	Map[x[0]][make_pair(x[1], x[2])] = Z + 1;
	return Z;
}

void dfs(int pos) {
	passed[pos] = true; int cnts = 0;
	for (int i = 0; i < G[pos].size(); i++) {
		if (passed[G[pos][i]] == true) continue;
		dfs(G[pos][i]); cnts++;
	}
	if (cnts == 0) I.push_back(pos);
}

void dfs2(int pos, int to) {
	if (pos == to) { J2 = J1; return; }
	passed[pos] = true;
	for (int i = 0; i < G[pos].size(); i++) {
		if (passed[G[pos][i]] == true) continue;
		J1.push_back(G[pos][i]);
		dfs2(G[pos][i], to);
		J1.pop_back();
	}
}

vector<int> getpath(int u, int v) {
	J1.clear(); J2.clear();
	J1.push_back(u);
	dfs2(u, v);
	return J2;
}

int getlca(int root, vector<pair<int, int>> E) {
	vector<int> cand; I.clear();
	for (int i = 0; i < E.size(); i++) cand.push_back(E[i].first);
	for (int i = 0; i < E.size(); i++) cand.push_back(E[i].second);
	for (int i : cand) G[i].clear();
	for (int i : cand) passed[i] = false;
	for (int i : cand) forced[i] = false;

	for (int i = 0; i < E.size(); i++) {
		G[E[i].first].push_back(E[i].second);
		G[E[i].second].push_back(E[i].first);
	}
	dfs(E[0].first);
	if (G[E[0].first].size() == 1) I.push_back(E[0].first);

	int mi = I.size() / 2;
	for (int i = mi; i < I.size(); i++) {
		int R = Ask(root, I[i - mi], I[i]); ret3++;
		for (int j : cand) passed[j] = false;
		vector<int> C1 = getpath(I[i - mi], R);
		for (int j = 0; j < C1.size() - 1; j++) forced[C1[j]] = true;
		for (int j : cand) passed[j] = false;
		vector<int> C2 = getpath(I[i], R);
		for (int j = 0; j < C2.size() - 1; j++) forced[C2[j]] = true;
	}

	for (int i : cand) {
		if (forced[i] == false) return i;
	}
	return -1;
}

vector<pair<int, int>> dfs(vector<int> A) {
	if (A.size() == 1) {
		return vector<pair<int, int>>{};
	}
	else if (A.size() == 2) {
		return vector<pair<int, int>>{make_pair(A[0], A[1])};
	}
	else if (A.size() == 3) {
		ret4++;
		int R = Ask(A[0], A[1], A[2]);
		vector<pair<int, int>> E;
		for (int i : A) { if (i != R) E.push_back(make_pair(i, R)); }
		return E;
	}
	else if (A.size() == 4) {
		vector<int> G1[24], G2[24];
		for (int i = 1; i < A.size(); i++) {
			for (int j = i + 1; j < A.size(); j++) {
				int V = Ask(A[0], A[i], A[j]); ret4++;
				if (V == A[i]) { G1[i].push_back(j); G2[j].push_back(i); }
				if (V == A[j]) { G1[j].push_back(i); G2[i].push_back(j); }
			}
		}
		vector<int> dist(24, 0);
		for (int i = 0; i < A.size(); i++) {
			for (int j = 0; j < A.size(); j++) {
				for (int k : G1[j]) dist[k] = max(dist[k], dist[j] + 1);
			}
		}
		vector<pair<int, int>> E;
		for (int i = 1; i < A.size(); i++) {
			int s = 0;
			for (int j : G2[i]) {
				if (dist[j] == dist[i] - 1) s = j;
			}
			E.push_back(make_pair(A[i], A[s]));
		}
		return E;
	}
	else {
		allret += A.size();
		//cout << allret << " " << A.size() << endl;
	}

	// 重心っぽい頂点を見つける
	int grav = -1;
	while (true) {
		int s = rand() % A.size(), cnt = 0; bool flag = false;
		int maxlim = 0;
		if (A.size() <= 7) maxlim = 0;
		else if (A.size() <= 20) maxlim = 1;
		else if (A.size() <= 50) maxlim = 3;
		else if (A.size() <= 200) maxlim = 6;
		else if (A.size() <= 500) maxlim = 13;
		else if (A.size() <= 1000) maxlim = 24;
		else if (A.size() <= 2000) maxlim = 37;
		for (int i = 1; i <= maxlim; i++) {
			int t = -1, u = -1;
			while (A[s] == t || t == u || A[s] == u) {
				t = A[rand() % A.size()];
				u = A[rand() % A.size()];
			}
			ret1++;
			if (Ask(A[s], t, u) == A[s]) cnt++;
			if (i == 1 && cnt <= 0) { flag = true; break; }
			if (i == 3 && cnt <= 1) { flag = true; break; }
			if (i == 6 && cnt <= 2) { flag = true; break; }
			if (i == 9 && cnt <= 3) { flag = true; break; }
			if (i == 13 && cnt <= 4) { flag = true; break; }
			if (i == 16 && cnt <= 5) { flag = true; break; }
			if (i == 20 && cnt <= 6) { flag = true; break; }
			if (i == 24 && cnt <= 7) { flag = true; break; }
			if (i == 28 && cnt <= 8) { flag = true; break; }
			if (i == 32 && cnt <= 9) { flag = true; break; }
			if (i == 37 && cnt <= 10) { flag = true; break; }
		}
		if (flag == false) { grav = s; break; }
	}
	//cout << A.size() << " " << ret1 << endl;

	// 重心分解をする
	vector<int> cand;
	for (int i = 0; i < A.size(); i++) { if (i != grav) cand.push_back(i); }
	for (int i = 0; i < A.size() * 20; i++) swap(cand[rand() % cand.size()], cand[rand() % cand.size()]);

	vector<vector<int>> centroid;
	for (int i : cand) {
		vector<pair<int, int>> Z;
		for (int j = 0; j < centroid.size(); j++) Z.push_back(make_pair(centroid[j].size(), j));
		sort(Z.begin(), Z.end());
		reverse(Z.begin(), Z.end());

		if (Z.size() == 0) {
			centroid.push_back(vector<int>{A[i]});
		}
		else {
			double method1 = 0, method2 = 0; int rem = 0;
			for (int j = 0; j < Z.size(); j++) {
				method1 += 1.0 * (double)(j + 1) * Z[j].first;
				if (Z.size() % 2 == 0) method2 += 1.0 * (double)((j / 2) + 2) * Z[j].first;
				if (Z.size() % 2 == 1) {
					if (j == 0) method2 += 1.0 * Z[j].first;
					else method2 += 1.0 * (double)((j + 1) / 2 + 2) * Z[j].first;
				}
			}

			bool flag = false; 
			if (method1 < method2) {
				for (int j = 0; j < Z.size(); j++) {
					int num = Z[j].second;
					int root = centroid[num][0];
					int V = Ask(A[grav], A[i], root); ret2++;
					if (V != A[grav]) { centroid[num].push_back(A[i]); flag = true; break; }
				}
			}
			else {
				int j = 0;
				while (j < (int)Z.size()) {
					if (j == 0 && Z.size() % 2 == 1) {
						int num = Z[j].second;
						int root = centroid[num][0];
						int V = Ask(A[grav], A[i], root); ret2++;
						if (V != A[grav]) { centroid[num].push_back(A[i]); flag = true; break; }
						j += 1;
					}
					else {
						int num1 = Z[j].second, num2 = Z[j + 1].second;
						int root1 = centroid[num1][0], root2 = centroid[num2][0];
						int V = Ask(root1, root2, A[i]); ret2++;
						if (V == A[grav]) { j += 2; continue; }
						int V1 = Ask(A[grav], A[i], root1); ret2++;
						if (V1 != A[grav]) { centroid[num1].push_back(A[i]); flag = true; break; }
						if (V1 == A[grav]) { centroid[num2].push_back(A[i]); flag = true; break; }
						j += 2;
					}
				}
			}
			if (flag == false) centroid.push_back(vector<int>{A[i]});
		}
	}

	// 復元をする
	vector<pair<int, int>> ans;
	for (vector<int> f : centroid) {
		vector<pair<int, int>> Z = dfs(f);
		for (pair<int, int> i : Z) ans.push_back(i);
		int U = f[0];
		if (Z.size() >= 1) U = getlca(A[grav], Z);
		ans.push_back(make_pair(A[grav], U));
	}
	return ans;
}

void Solve(int N) {
	vector<int> L;
	for (int i = 0; i < N; i++) L.push_back(i);

	vector<pair<int, int>> V = dfs(L);

	for (int i = 0; i < V.size(); i++) {
		if (V[i].first > V[i].second) swap(V[i].first, V[i].second);
		Bridge(V[i].first, V[i].second);
	}
	return;
}

Compilation message (stderr)

meetings.cpp: In function 'void dfs(int)':
meetings.cpp:31:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < G[pos].size(); i++) {
                  ~~^~~~~~~~~~~~~~~
meetings.cpp: In function 'void dfs2(int, int)':
meetings.cpp:41:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < G[pos].size(); i++) {
                  ~~^~~~~~~~~~~~~~~
meetings.cpp: In function 'int getlca(int, std::vector<std::pair<int, int> >)':
meetings.cpp:58:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < E.size(); i++) cand.push_back(E[i].first);
                  ~~^~~~~~~~~~
meetings.cpp:59:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < E.size(); i++) cand.push_back(E[i].second);
                  ~~^~~~~~~~~~
meetings.cpp:64:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < E.size(); i++) {
                  ~~^~~~~~~~~~
meetings.cpp:72:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = mi; i < I.size(); i++) {
                   ~~^~~~~~~~~~
meetings.cpp:76:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int j = 0; j < C1.size() - 1; j++) forced[C1[j]] = true;
                   ~~^~~~~~~~~~~~~~~
meetings.cpp:79:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int j = 0; j < C2.size() - 1; j++) forced[C2[j]] = true;
                   ~~^~~~~~~~~~~~~~~
meetings.cpp: In function 'std::vector<std::pair<int, int> > dfs(std::vector<int>)':
meetings.cpp:104:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int i = 1; i < A.size(); i++) {
                   ~~^~~~~~~~~~
meetings.cpp:105:26: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for (int j = i + 1; j < A.size(); j++) {
                        ~~^~~~~~~~~~
meetings.cpp:112:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int i = 0; i < A.size(); i++) {
                   ~~^~~~~~~~~~
meetings.cpp:113:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for (int j = 0; j < A.size(); j++) {
                    ~~^~~~~~~~~~
meetings.cpp:118:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int i = 1; i < A.size(); i++) {
                   ~~^~~~~~~~~~
meetings.cpp:170:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < A.size(); i++) { if (i != grav) cand.push_back(i); }
                  ~~^~~~~~~~~~
meetings.cpp:171:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < A.size() * 20; i++) swap(cand[rand() % cand.size()], cand[rand() % cand.size()]);
                  ~~^~~~~~~~~~~~~~~
meetings.cpp:176:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int j = 0; j < centroid.size(); j++) Z.push_back(make_pair(centroid[j].size(), j));
                   ~~^~~~~~~~~~~~~~~~~
meetings.cpp:185:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for (int j = 0; j < Z.size(); j++) {
                    ~~^~~~~~~~~~
meetings.cpp:196:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int j = 0; j < Z.size(); j++) {
                     ~~^~~~~~~~~~
meetings.cpp:184:41: warning: unused variable 'rem' [-Wunused-variable]
    double method1 = 0, method2 = 0; int rem = 0;
                                         ^~~
meetings.cpp: In function 'void Solve(int)':
meetings.cpp:247:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < V.size(); i++) {
                  ~~^~~~~~~~~~

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