Submission #131539

#	Time	Username	Problem	Language	Result	Execution time	Memory
131539		SirCeness	Meetings (JOI19_meetings)	C++14	29 / 100	2066 ms	984 KiB

meetings

#include "meetings.h"
#include <bits/stdc++.h>

using namespace std;
#define ll long long;
#define mod 1000000007
#define mp make_pair
#define pb push_back
#define bas(x) #x << ": " << x
#define prarr(x, n) cout << #x << ": "; for (int qsd = 0; qsd < n; qsd++) cout << x[qsd] << " "; cout << endl;
#define prarrv(x) cout << #x << ": "; for (int qsd = 0; qsd < (int)x.size(); qsd++) cout << x[qsd] << " "; cout << endl;
#define inside sl<=l%&&r<=sr
#define outside sr<l||r<sl

void get(int root, vector<int>& arr){
	//cout << "get(" << root << ")" << endl;
	//prarrv(arr);
	if (arr.size() == 0) return;
	else if (arr.size() == 1){
		//cout << "bridge(" << root << ", " << arr[0] << ")" << endl;
		Bridge(min(root, arr[0]), max(root, arr[0]));
		return;
	}
	int ch = arr[rand()%arr.size()];
	vector<int> alt;
	vector<int> ust;
	vector<int> dig;
	ust.pb(ch);
	int en = ch;
	for (int i = 0; i < arr.size(); i++){
		//cout << "query(" << root << ", " << ch << ", " << arr[i] << ")" << endl;
		if (ch == arr[i]) continue;
		int ans = Query(root, ch, arr[i]);
		if (ans == ch){
			alt.pb(arr[i]);
		} else if (ans == root){
			dig.pb(arr[i]);
		} else {
			ust.pb(arr[i]);
			if (arr[i] != en) en = Query(root, arr[i], en);
		}
	}
	
	for (int i = 0; i < ust.size(); i++){
		if (ust[i] == en){
			int tmp = ust[ust.size()-1];
			ust[ust.size()-1] = ust[i];
			ust[i] = tmp;
			break;
		}
	}
	ust.pop_back();
	
	Bridge(min(root, en), max(root, en));
	get(root, dig);
	get(en, ust);
	get(ch, alt);
}

void Solve(int N) {
	srand(time(0));
	vector<int> arr(N-1);
	for (int i = 1; i < N; i++) arr[i-1] = i;
	get(0, arr);
}

Compilation message (stderr)

meetings.cpp: In function 'void get(int, std::vector<int>&)':
meetings.cpp:30:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < arr.size(); i++){
                  ~~^~~~~~~~~~~~
meetings.cpp:44:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < ust.size(); i++){
                  ~~^~~~~~~~~~~~

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