Submission #553782

#	Time	Username	Problem	Language	Result	Execution time	Memory
553782		MilosMilutinovic	Meetings (JOI19_meetings)	C++14	100 / 100	675 ms	2176 KiB

meetings

#include "meetings.h"
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <cmath>
#include <vector>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <queue>
#include <ctime>
#include <cassert>
#include <complex>
#include <string>
#include <cstring>
#include <chrono>
#include <random>
#include <bitset>
#include <array>
using namespace std;
 
#ifdef LOCAL
	#define eprintf(...) {fprintf(stderr, __VA_ARGS__);fflush(stderr);}
#else
	#define eprintf(...) 42
#endif
 
using ll = long long;
using ld = long double;
using uint = unsigned int;
using ull = unsigned long long;
template<typename T>
using pair2 = pair<T, T>;
using pii = pair<int, int>;
using pli = pair<ll, int>;
using pll = pair<ll, ll>;
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
ll myRand(ll B) {
	return (ull)rng() % B;
}
 
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second
 
clock_t startTime;
double getCurrentTime() {
	return (double)(clock() - startTime) / CLOCKS_PER_SEC;
}

map<int, vector<int>> mapchik;
vector<int> path;

void Answer(int u, int v) {
	Bridge(min(u, v), max(u, v));
}

void solve(vector<int> v) {
	if (v.size() < 2) return;
	shuffle(all(v), rng);
	int x = v[0], y = v[1];
	path.clear();
	mapchik[x].pb(x);
	mapchik[y].pb(y);
	for (int i = 2; i < v.size(); i++) {
		int p = Query(x, y, v[i]);
		if (mapchik[p].empty())
			path.pb(p);
		mapchik[p].pb(v[i]);
	}
	sort(all(path), [&](int i, int j) {
		return Query(x, i, j) == i;
	});
	int prv = x;
	for (int i = 0; i < path.size(); i++)
		Answer(prv, path[i]), prv = path[i];
	Answer(prv, y);
	vector<vector<int>> todo;
	for (auto it : mapchik)
		todo.pb(it.se);
	mapchik[x].clear();
	mapchik[y].clear();
	for (int i = 0; i < path.size(); i++)
		mapchik[path[i]].clear();
	for (auto it : todo)
		solve(it);
}

void Solve(int n) {
	vector<int> vec;
	for (int i = 0; i < n; i++)
		vec.pb(i);
	solve(vec);
}

Compilation message (stderr)

meetings.cpp: In function 'void solve(std::vector<int>)':
meetings.cpp:69:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   69 |  for (int i = 2; i < v.size(); i++) {
      |                  ~~^~~~~~~~~~
meetings.cpp:79:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   79 |  for (int i = 0; i < path.size(); i++)
      |                  ~~^~~~~~~~~~~~~
meetings.cpp:87:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   87 |  for (int i = 0; i < path.size(); i++)
      |                  ~~^~~~~~~~~~~~~

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