Submission #135493

#	Time	Username	Problem	Language	Result	Execution time	Memory
135493		eohomegrownapps	Meetings (JOI19_meetings)	C++14	29 / 100	2680 ms	8000 KiB

meetings

#include "meetings.h"
#include <bits/stdc++.h>
using namespace std;
//Query(int a, int b, int c)
//Bridge(int first, int second)
//edges from 0 to n-1

typedef long long ll;
ll acns = 100000000;
ll bcns = 10000;
unordered_map<ll,int> querymap;
int n;
int squery(int a, int b, int c){
	//cout<<"query "<<a<<" "<<b<<" "<<c<<endl;
	if (a>b){
		swap(a,b);
	}
	if (b>c){
		swap(b,c);
	}
	if (a>b){
		swap(a,b);
	}
	if (b>c){
		swap(b,c);
	}
	ll q = a*acns+b*bcns+c;
	auto f = querymap.find(q);
	if (f==querymap.end()){
		return querymap[q]=Query(a,b,c);
	} else {
		return (*f).second;
	}
}
int sortstart, sortend;
bool sfunction(int a, int b){
	return (squery(sortstart,a,b)==a);
}

void solverecursive(int start, vector<int> &arrayUsing){
	int row[2000];
	/*cout<<"===="<<endl;
	for (int i : arrayUsing){
		cout<<i<<" ";
	}cout<<endl;*/
	int end = arrayUsing[0];
	int ptr = 0;
	//deque<int> row;
	//row.push_back(start);
	//row.push_back(end);
	vector<vector<int> > children(n);
	for (int i = 1; i<arrayUsing.size(); i++){
		int node = squery(start,end,arrayUsing[i]);
		if (node==start){
			row[ptr]=start;
			ptr++;
			//row.push_front(arrayUsing[i]);
			start=arrayUsing[i];
		} else if (node==end){
			row[ptr]=end;
			ptr++;
			//row.push_back(arrayUsing[i]);
			end=arrayUsing[i];
		} else if (node==arrayUsing[i]){
			row[ptr]=node;
			ptr++;
			//row[row.size()-1]=node;
			//row.push_back(end);
		} else {
			children[node].push_back(arrayUsing[i]);
		}
	}
	//sort
	if (ptr>1){
		sortstart=start;
		sortend=end;
		sort(row,row+ptr,sfunction);
	}
	/*cout<<start<<" ";
	for (int i = 0; i<ptr; i++){
		cout<<row[i]<<" ";
	}cout<<end<<" "<<endl;*/
	//cout<<"bridge "<<min(start,row[0])<<" "<<max(start,row[0])<<endl;
	Bridge(min(start,row[0]),max(start,row[0]));
	row[ptr]=end;
	for (int i = 0; i<ptr; i++){
		//cout<<"bridge "<<min(row[i],row[i+1])<<" "<<max(row[i],row[i+1])<<endl;
		Bridge(min(row[i],row[i+1]),max(row[i],row[i+1]));
		if (children[row[i]].size()==0){
			continue;
		} else if (children[row[i]].size()==1){
			//cout<<"bridge "<<min(row[i],children[row[i]][0])<<" "<<max(row[i],children[row[i]][0])<<endl;
			Bridge(min(row[i],children[row[i]][0]),max(row[i],children[row[i]][0]));
		} else {
			solverecursive(row[i],children[row[i]]);
		}
	}//add case where i=row.size()-1

}
void Solve(int N) {
	n = N;
	vector<int> arrayUsing;
	arrayUsing.resize(n-1,0);
	for (int i = 1; i<n; i++){
		arrayUsing[i-1]=i;
	}
	solverecursive(0,arrayUsing);
}

Compilation message (stderr)

meetings.cpp: In function 'void solverecursive(int, std::vector<int>&)':
meetings.cpp:52:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 1; i<arrayUsing.size(); i++){
                  ~^~~~~~~~~~~~~~~~~~

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