Submission #726693

#	Time	Username	Problem	Language	Result	Execution time	Memory
726693		josanneo22	Meetings (JOI19_meetings)	C++17	0 / 100	370 ms	564 KiB

meetings

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
 
#include "meetings.h"

using namespace std;
using namespace __gnu_pbds;
 
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define fbo find_by_order
#define ook order_of_key
 
typedef long long ll;
typedef pair<int,int> ii;
typedef vector<int> vi;
typedef long double ld; 
typedef tree<ll, null_type, less<ll>, rb_tree_tag, tree_order_statistics_node_update> pbds;
typedef set<ll>::iterator sit;
typedef map<ll,ll>::iterator mit;

int Q;
int query(int a, int b, int c)
{
	return Query(a,b,c);
}

int N;
vector<ii> edges;

void out()
{
	for(int i=0;i<edges.size();i++)
	{
		Bridge(edges[i].fi,edges[i].se);
	}
}

void addedge(int x, int y)
{
	edges.pb(mp(x,y));
}

int A,B;

bool cmp(int x, int y)
{
	if(x==A) return true;
	if(x==B) return false;
	if(y==A) return false;
	if(y==B) return true;
	int z=query(A,x,y);
	if(z==x) return true;
	else return false;
}

void solve(vi vec)
{
	int n=vec.size();
	if(n==1) return;
	if(n==2)
	{
		addedge(vec[0],vec[1]);
		return ;
	}
	random_shuffle(vec.begin(),vec.end());
	map<int,vi> ma;
	for(int i=2;i<n;i++)
	{
		int x=query(vec[0],vec[1],vec[i]);
		ma[x].pb(vec[i]);
	}
	A=vec[0];B=vec[1];
	vi path;
	for(auto it = ma.begin(); it != ma.end(); it++)
	{
		path.pb(it->fi);
	}
	path.pb(A); path.pb(B);
	sort(path.begin(),path.end()); path.erase(unique(path.begin(),path.end()),path.end());
	sort(path.begin(),path.end(),cmp);
	for(int i=0;i+1<path.size();i++)
	{
		addedge(path[i],path[i+1]);
	}
	for(auto it = ma.begin(); it != ma.end(); it++)
	{
		if(it->fi==A) it->se.pb(A);
		if(it->fi==B) it->se.pb(B);
		
	}
	for(auto it = ma.begin(); it != ma.end(); it++)
	{
		solve(it->se);
	}
}
void Solve(int N) {
  	vi vec;
	for(int i=0;i<N;i++) vec.pb(i);
	solve(vec);
	out();
}

Compilation message (stderr)

meetings.cpp: In function 'void out()':
meetings.cpp:36:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   36 |  for(int i=0;i<edges.size();i++)
      |              ~^~~~~~~~~~~~~
meetings.cpp: In function 'void solve(vi)':
meetings.cpp:85:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   85 |  for(int i=0;i+1<path.size();i++)
      |              ~~~^~~~~~~~~~~~

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