Submission #128391

#	Time	Username	Problem	Language	Result	Execution time	Memory
128391		wilwxk	Meetings (JOI19_meetings)	C++14	100 / 100	1036 ms	964 KiB

meetings

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

const int MAXN=2e3+5;
vector<int> bons[MAXN];
mt19937 rng(time(0));
int n, A, B;

int ask(int a, int b, int c) {
	if(a==b||a==c) return a;
	if(b==c) return b;
	return Query(a, b, c);
}
bool cmp(int a, int b) {
	return ask(a, b, A)==a;
}
void liga(int a, int b) {
	if(a>b) swap(a, b);
	Bridge(a, b);
}

void solve(int raiz) {
	if(bons[raiz].size()<=1) return; //marc[raiz]=1;
	vector<int> linha, aux=bons[raiz]; bons[raiz].clear();
	int a=rng()%aux.size(), b=rng()%aux.size();
	while(a==b) b=rng()%aux.size();
	a=aux[a]; b=aux[b];

	// printf("solving %d >> %d e %d\n", raiz, a, b, bons[raiz].size());
	// for(auto cara : aux) printf("%d ", cara); printf("|||\n");
	for(auto cur : aux) {
		int cara=ask(cur, a, b);
		bons[cara].push_back(cur);
		linha.push_back(cara);
	}
	sort(linha.begin(), linha.end()); auto it=unique(linha.begin(), linha.end()); linha.resize(it-linha.begin());
	A=a; B=b; sort(linha.begin(), linha.end(), cmp);
	// for(auto cur : linha) printf("linha_ord %d // %d %d // %d\n", cur, a, b, linha.size(), it-linha.begin());
	for(int i=1; i<linha.size(); i++) liga(linha[i], linha[i-1]);
	for(auto cur : linha) solve(cur);
}

void Solve(int N) {
	n=N;
	for(int i=0; i<n; i++) bons[n].push_back(i);
	solve(n);
}

Compilation message (stderr)

meetings.cpp: In function 'void solve(int)':
meetings.cpp:40:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=1; i<linha.size(); i++) liga(linha[i], linha[i-1]);
               ~^~~~~~~~~~~~~

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