Submission #119795

#	Time	Username	Problem	Language	Result	Execution time	Memory
119795		patrikpavic2	Meetings (JOI19_meetings)	C++17	100 / 100	1323 ms	1144 KiB

meetings

#include "meetings.h"
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cstdlib>
#include <vector>

using namespace std;

#define PB push_back

const int N = 2005;

typedef vector < int > vi;

int sp, n;
vi tr[N];

bool cmp(int i,int j){
	//printf("pitam2 %d %d %d\n", sp, i , j);
	if(sp == i) return 0;
	if(sp == j) return 1;
	return Query(sp, i, j) == j;
}

void rek(vi v, int root){
	if(v.size() == 0) return;
	int x = v[rand() % v.size()];
	//printf("root = %d\n", root);
	//printf("podstablo = ");
	//for(int xx : v) printf("%d ", xx);
	//printf("\n");
	//printf("X = %d\n", x);
	vi pos = {root, x};
	for(int y : v){
		if(y == x) continue;
		int res = Query(x, y, root);
		//printf("pitam %d %d %d => %d\n", x, y, root, res);
		if(res == y) pos.PB(y);
		else tr[res].PB(y);// printf("y %d pripada %d\n", y, res);
	}
	//printf("pos : %d\n", pos.size());
	sp = root; sort(pos.begin(), pos.end(), cmp);
	for(int i = 1;i < pos.size();i++)
		Bridge(min(pos[i - 1], pos[i]), max(pos[i - 1], pos[i]));// printf("edge %d %d\n", pos[i - 1], pos[i]);
	for(int nxt : pos){
		vi tmp = tr[nxt]; tr[nxt].clear();
		rek(tmp, nxt);
	}
}

void Solve(int nn) {
	n = nn;
 	int root = rand() % n;
 	vi st;
 	for(int i = 0;i < n;i++)
 		if(i != root)
 			st.PB(i);
	rek(st, root);
}

Compilation message (stderr)

meetings.cpp: In function 'void rek(vi, int)':
meetings.cpp:44:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 1;i < pos.size();i++)
                ~~^~~~~~~~~~~~

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