Submission #123966

#	Time	Username	Problem	Language	Result	Execution time	Memory
123966		sebinkim	Meetings (JOI19_meetings)	C++14	100 / 100	1104 ms	888 KiB

meetings

#include <bits/stdc++.h>

#include "meetings.h"

using namespace std;

typedef pair <int, int> pii;

void bridge(int u, int v)
{
	if(u > v) swap(u, v);
	Bridge(u, v);
}

void f(int p, vector <int> &V)
{
	vector <int> X;
	vector <pii> Y;
	int i, j, v, q;
	
	swap(V[rand() % V.size()], V.back());
	q = V.back(); V.pop_back();
	
	for(int &t: V){
		v = Query(p, q, t);
		if(t == v) X.push_back(t);
		else Y.emplace_back(v, t);
	}
	
	if(X.empty()) bridge(p, q);
	else{
		sort(X.begin(), X.end(), [&](int &a, int &b){
			if(a == b) return false;
			return Query(p, a, b) == a;
		});
		
		bridge(p, X[0]);
		for(i=1; i<X.size(); i++){
			bridge(X[i - 1], X[i]);
		}
		bridge(X.back(), q);
	}
	
	sort(Y.begin(), Y.end());
	
	for(i=0; i<Y.size(); i=j){
		V.clear();
		for(j=i; j<Y.size() && Y[j].first == Y[i].first; j++){
			V.push_back(Y[j].second);
		}
		f(Y[i].first, V);
	}
}

void Solve(int n)
{
	vector <int> V;
	int i;
	
	srand(time(0));
	
	for(i=1; i<n; i++){
		V.push_back(i);
	}
	
	f(0, V);
}

Compilation message (stderr)

meetings.cpp: In function 'void f(int, std::vector<int>&)':
meetings.cpp:38:13: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(i=1; i<X.size(); i++){
            ~^~~~~~~~~
meetings.cpp:46:12: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(i=0; i<Y.size(); i=j){
           ~^~~~~~~~~
meetings.cpp:48:13: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(j=i; j<Y.size() && Y[j].first == Y[i].first; j++){
            ~^~~~~~~~~

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