Submission #620769

#	Time	Username	Problem	Language	Result	Execution time	Memory
620769		jamezzz	Meetings (JOI19_meetings)	C++17	100 / 100	1111 ms	944 KiB

meetings

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

#define maxn 2005
#define all(x) x.begin(),x.end()
#define disc(x) sort(all(x));x.resize(unique(all(x))-x.begin());
mt19937 rng(218);

vector<int> sub[maxn];

void subtree(int rt,vector<int> nodes){
	//printf("subtree %d: ",rt);
	//for(int i:nodes)printf("%d ",i);
	//printf("\n");
	int n=nodes.size(),far;
	do{
		far=nodes[rng()%n];
	}while(far==rt);
	for(int i:nodes)sub[i].clear();
	vector<int> line;
	line.push_back(rt);
	line.push_back(far);
	sub[rt].push_back(rt);
	sub[far].push_back(far);
	for(int i:nodes){
		if(i==rt||i==far)continue;
		//printf("query: %d %d %d\n",rt,far,i);
		int par=Query(rt,far,i);
		line.push_back(par);
		sub[par].push_back(i);
	}
	
	disc(line);
	sort(all(line),[&](int a,int b){
		if(a==rt)return true;
		if(b==rt)return false;
		return Query(rt,a,b)==a;
	});
	for(int i=1;i<line.size();++i){
		if(line[i-1]<line[i])Bridge(line[i-1],line[i]);
		else Bridge(line[i],line[i-1]);
	}
	
	for(int i:line){
		if(sub[i].size()==1)continue;
		subtree(i,sub[i]);
	}
}

void Solve(int n){
	vector<int> v;
	for(int i=0;i<n;++i)v.push_back(i);
	subtree(rng()%n,v);
}

Compilation message (stderr)

meetings.cpp: In function 'void subtree(int, std::vector<int>)':
meetings.cpp:40:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   40 |  for(int i=1;i<line.size();++i){
      |              ~^~~~~~~~~~~~

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