Submission #210468

#	Time	Username	Problem	Language	Result	Execution time	Memory
210468		mhy908	Meetings (JOI19_meetings)	C++14	100 / 100	1025 ms	956 KiB

meetings

#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#include "meetings.h"
#include <bits/stdc++.h>
#define pb push_back
#define all(x) x.begin(), x.end()
using namespace std;
int st, fin;
bool comp(int a, int b){
    if(a==st||b==fin)return 1;
    if(a==fin||b==st)return 0;
    return Query(st, a, b)==a;
}
unordered_map<int, vector<int> > ump;
void solve(vector<int> vc){
	if(vc.size()<=1)return;
	st=rand()%vc.size();
	fin=(st+rand()%(vc.size()-1)+1)%vc.size();
	st=vc[st], fin=vc[fin];
	ump[st].pb(st);
	ump[fin].pb(fin);
	vector<int> path;
	path.pb(st);
	for(int i=0; i<vc.size(); i++){
        if(vc[i]==st||vc[i]==fin)continue;
		int x=Query(st, fin, vc[i]);
		if(ump[x].empty())path.pb(x);
		ump[x].pb(vc[i]);
	}
	path.pb(fin);
	sort(all(path), comp);
	for(int i=0; i<path.size()-1; i++){
        Bridge(min(path[i], path[i+1]), max(path[i], path[i+1]));
	}
	for(int i=0; i<path.size(); i++){
		vector<int> temp=ump[path[i]];
		ump[path[i]].clear();
		solve(temp);
	}
}
void Solve(int n){
    srand(time(NULL));
	vector<int> temp;
	for(int i=0; i<n; i++)temp.pb(i);
	solve(temp);
}

Compilation message (stderr)

meetings.cpp: In function 'void solve(std::vector<int>)':
meetings.cpp:25:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0; i<vc.size(); i++){
               ~^~~~~~~~~~
meetings.cpp:33:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0; i<path.size()-1; i++){
               ~^~~~~~~~~~~~~~
meetings.cpp:36:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0; i<path.size(); i++){
               ~^~~~~~~~~~~~

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