Submission #226799

#	Time	Username	Problem	Language	Result	Execution time	Memory
226799		kshitij_sodani	Meetings (JOI19_meetings)	C++17	100 / 100	660 ms	2168 KiB

meetings

#include <iostream>
#include <bits/stdc++.h>
using namespace std;
typedef int64_t llo;
#define mp make_pair
#define pb push_back
#define a first
#define b second
#define endl "\n"
#include "meetings.h"
mt19937 rng;
/*void Bridge(int u,int v){
	cout<<u<<" "<<v<<endl;
}
int Query(int u,int v,int x){
	cout<<u<<" "<<v<<" "<<x<<endl;
	int x2;
	cin>>x2;
	return x2;
}*/
int par[2001];
int par4;
int n;
vector<pair<int,int>> ans;
bool sort_by(int u,int v){
	return Query(par4,u,v)==u;
}
void solve2(vector<int> v){
	
	shuffle(v.begin(),v.end(),rng);
	int st=v[0];
	int en=v[1];

	vector<int> sub[n];
	set<int> now;
	now.insert(st);
	now.insert(en);
	for(auto i:v){
		if(i==st or i==en){
			continue;
		}
		int x=Query(st,en,i);
		now.insert(x);
		if(i!=x){
			sub[x].pb(i);
		}
	}
	vector<int> ss;
	for(auto j:now){
		if(j!=st){
			ss.pb(j);
		}
	}
	par4=st;
	sort(ss.begin(),ss.end(),sort_by);
	//cout<<ss.size()<<endl;
	for(int i=0;i<ss.size();i++){
		if(i==0){
			par[ss[i]]=par4;
			ans.pb({ss[i],par4});
		}
		else{
			par[ss[i]]=ss[i-1];
			ans.pb({ss[i],ss[i-1]});
		}
	}
	for(auto j:now){
		if(sub[j].size()>0){
			sub[j].pb(j);
			solve2(sub[j]);
		}
	}
}
void Solve(int nn){
	n=nn;
	ans.clear();
	rng= mt19937(chrono::steady_clock::now().time_since_epoch().count());
	for(int i=0;i<n;i++){
		par[i]=-1;
	}
	vector<int> kk;
	for(int i=0;i<n;i++){
		kk.pb(i);
	}
	solve2(kk);

	for(auto i:ans){
		Bridge(min(i.a,i.b),max(i.a,i.b));
	}
}

/*int main(){
	Solve(3);


	return 0;
}*/

Compilation message (stderr)

meetings.cpp: In function 'void solve2(std::vector<int>)':
meetings.cpp:57:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<ss.size();i++){
              ~^~~~~~~~~~

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