Submission #532007

#	Time	Username	Problem	Language	Result	Execution time	Memory
532007		fhvirus	Meetings (JOI19_meetings)	C++17	100 / 100	1085 ms	16464 KiB

meetings

#include "meetings.h"
#include <bits/stdc++.h>
using namespace std;
typedef int64_t ll; typedef pair<int, int> pii;
#define pb emplace_back
#define AI(x) begin(x),end(x)
#define ff first
#define ss second
#ifdef OWO
#define debug(args...) LKJ("\033[1;32m[ " + string(#args) + " ]\033[0m", args)
template <class I> void LKJ(I&&x) { cerr << x << endl; }
template <class I, class...T> void LKJ(I&&x, T&&...t) { cerr << x << ", "; LKJ(t...); }
template <class I> void OI(I a, I b) { while (a != b) cerr << *a << " \n"[(a = next(a)) == b]; }
#else
#define debug(...) 0
#define OI(...) 0
#endif

namespace {

random_device rd;
mt19937 mt(rd());

const int kN = 2002;
int N, root, mem[kN][kN];

int queryLCA(int u, int v) {
	assert(u != v);
	if (mem[u][v] != -1) return mem[u][v];
	return (mem[u][v] = Query(root, u, v));
}
void addEdge(int u, int v) {
	if (u > v) swap(u, v);
	debug("Add edge", u, v);
	Bridge(u, v);
}

bool cmp(int u, int v) {
	return queryLCA(u, v) == u;
}

void init(int N) {
	::N = N;
	for (int i = 0; i < N; ++i)
		for (int j = 0; j < N; ++j)
			mem[i][j] = -1;
}

void solve(int rt, vector<int> ids) {
	debug(rt);
	OI(AI(ids));
	if (ids.empty()) return;
	if (ids.size() == 1) {
		addEdge(rt, ids[0]);
		return;
	}

	int u = ids.back(); ids.pop_back();
	map<int, vector<int>> mp;
	vector<int> ps;
	for (const int& v: ids) {
		int lca = queryLCA(u, v);
		if (lca == v and lca != u) ps.pb(lca);
		else mp[lca].pb(v);
	}

	debug(u);
	for (auto &[nrt, nids]: mp) {
		debug(nrt);
		OI(AI(nids));
	}

	if (ps.empty()) {
		addEdge(rt, u);
	} else {
		sort(AI(ps));
		ps.erase(unique(AI(ps)), end(ps));
		sort(AI(ps), cmp);
		debug("ps");
		OI(AI(ps));

		addEdge(rt, ps[0]);
		addEdge(ps.back(), u);
		for (int i = 1; i < ps.size(); ++i)
			addEdge(ps[i - 1], ps[i]);
	}

	for (auto &[nrt, nids]: mp) {
		shuffle(AI(nids), mt);
		solve(nrt, nids);
	}
}

} // namespace

void Solve(int N) {
	init(N);

	vector<int> ids(N);
	iota(AI(ids), 0);
	shuffle(AI(ids), mt);

	root = ids.back();
	ids.pop_back();

	debug(root);
	OI(AI(ids));
	solve(root, ids);

	/*
  for (int u = 0; u < N - 1; ++u)
    Bridge(u, u + 1);
	*/
}

Compilation message (stderr)

meetings.cpp: In function 'void {anonymous}::addEdge(int, int)':
meetings.cpp:15:20: warning: statement has no effect [-Wunused-value]
   15 | #define debug(...) 0
      |                    ^
meetings.cpp:34:2: note: in expansion of macro 'debug'
   34 |  debug("Add edge", u, v);
      |  ^~~~~
meetings.cpp: In function 'void {anonymous}::solve(int, std::vector<int>)':
meetings.cpp:15:20: warning: statement has no effect [-Wunused-value]
   15 | #define debug(...) 0
      |                    ^
meetings.cpp:50:2: note: in expansion of macro 'debug'
   50 |  debug(rt);
      |  ^~~~~
meetings.cpp:16:17: warning: statement has no effect [-Wunused-value]
   16 | #define OI(...) 0
      |                 ^
meetings.cpp:51:2: note: in expansion of macro 'OI'
   51 |  OI(AI(ids));
      |  ^~
meetings.cpp:15:20: warning: statement has no effect [-Wunused-value]
   15 | #define debug(...) 0
      |                    ^
meetings.cpp:67:2: note: in expansion of macro 'debug'
   67 |  debug(u);
      |  ^~~~~
meetings.cpp:15:20: warning: statement has no effect [-Wunused-value]
   15 | #define debug(...) 0
      |                    ^
meetings.cpp:69:3: note: in expansion of macro 'debug'
   69 |   debug(nrt);
      |   ^~~~~
meetings.cpp:16:17: warning: statement has no effect [-Wunused-value]
   16 | #define OI(...) 0
      |                 ^
meetings.cpp:70:3: note: in expansion of macro 'OI'
   70 |   OI(AI(nids));
      |   ^~
meetings.cpp:68:13: warning: unused structured binding declaration [-Wunused-variable]
   68 |  for (auto &[nrt, nids]: mp) {
      |             ^~~~~~~~~~~
meetings.cpp:15:20: warning: statement has no effect [-Wunused-value]
   15 | #define debug(...) 0
      |                    ^
meetings.cpp:79:3: note: in expansion of macro 'debug'
   79 |   debug("ps");
      |   ^~~~~
meetings.cpp:16:17: warning: statement has no effect [-Wunused-value]
   16 | #define OI(...) 0
      |                 ^
meetings.cpp:80:3: note: in expansion of macro 'OI'
   80 |   OI(AI(ps));
      |   ^~
meetings.cpp:84:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   84 |   for (int i = 1; i < ps.size(); ++i)
      |                   ~~^~~~~~~~~~~
meetings.cpp: In function 'void Solve(int)':
meetings.cpp:15:20: warning: statement has no effect [-Wunused-value]
   15 | #define debug(...) 0
      |                    ^
meetings.cpp:106:2: note: in expansion of macro 'debug'
  106 |  debug(root);
      |  ^~~~~
meetings.cpp:16:17: warning: statement has no effect [-Wunused-value]
   16 | #define OI(...) 0
      |                 ^
meetings.cpp:107:2: note: in expansion of macro 'OI'
  107 |  OI(AI(ids));
      |  ^~

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