Submission #170655

#	Time	Username	Problem	Language	Result	Execution time	Memory
170655		arnold518	Meetings (JOI19_meetings)	C++14	100 / 100	715 ms	936 KiB

meetings

#include "meetings.h"
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

int N;

mt19937 gen(time(NULL));

int rand(int l, int r)
{
	uniform_int_distribution<> dis(l, r);
	return dis(gen);
}

void answer(int a, int b)
{
	if(a>b) swap(a, b);
	Bridge(a, b);
}

void solve(vector<int> cand)
{
	if(cand.size()==1) return;
	int i, j;
	int u, v;

	u=rand(0, cand.size()-1);
	v=rand(0, cand.size()-1);
	while(u==v) v=rand(0, cand.size()-1);

	u=cand[u]; v=cand[v];

	map<int, vector<int>> M;
	vector<int> V;

	M[u].push_back(u);
	M[v].push_back(v);

	for(auto now : cand)
	{
		if(now==u || now==v) continue;
		int t=Query(u, v, now);
		M[t].push_back(now);
		if(t!=u && t!=v) V.push_back(t);
	}

	sort(V.begin(), V.end());
	V.erase(unique(V.begin(), V.end()), V.end());
	sort(V.begin(), V.end(), [&](const int &p, const int &q)
	{
		return Query(u, p, q)==p;
	});

	V.insert(V.begin(), u);
	V.push_back(v);

	for(i=1; i<V.size(); i++) answer(V[i], V[i-1]);

	for(auto it : M) solve(it.second);
}

void Solve(int _N)
{
	int i, j;
	N=_N;

	vector<int> V;
	for(i=0; i<N; i++) V.push_back(i);
	solve(V);
}

Compilation message (stderr)

meetings.cpp: In function 'void solve(std::vector<int>)':
meetings.cpp:61:12: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(i=1; i<V.size(); i++) answer(V[i], V[i-1]);
           ~^~~~~~~~~
meetings.cpp:28:9: warning: unused variable 'j' [-Wunused-variable]
  int i, j;
         ^
meetings.cpp: In function 'void Solve(int)':
meetings.cpp:68:9: warning: unused variable 'j' [-Wunused-variable]
  int i, j;
         ^

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