Submission #151920

#	Time	Username	Problem	Language	Result	Execution time	Memory
151920		username	Meetings (JOI19_meetings)	C++14	100 / 100	1424 ms	3340 KiB

meetings

#include "meetings.h"
#define VIS(it,con) for(auto it=con.begin();it!=con.end();++it)
#include<bits/stdc++.h>
//#define int int_fast64_t
using namespace std;
typedef pair<int,int> pii;
#define REP(i,j,k) for(register int i=(j);i<(k);++i)
#define RREP(i,j,k) for(register int i=int(j)-1;i>=(k);--i)
#define ALL(a) a.begin(),a.end()
#define pb push_back
#define f first
#define s second
#define de(...) cerr<<__VA_ARGS__
#define ar(a,s,t) {REP(__i,s,t)de(a[__i]<<' ');de(endl);}
 
mt19937 rd(time(0));
int o;
map<pii,int>rec;
 
int qr(int a,int b){
	if(rec.count({a,b}))return rec[{a,b}];
	int ret=a==b?a:a==o||b==o?o:Query(o,a,b);
	rec[{a,b}]=ret;
	return ret;
}
 
void solve(int rt,vector<int>v){
	if(v.size()==1)return;
	int u=rt;
	while(u==rt)u=v[rd()%v.size()];
	map<int,vector<int>>mp;
	REP(i,0,v.size())mp[qr(u,v[i])].pb(v[i]);
	vector<int>path;
	VIS(it,mp){
		solve(it->f,it->s);
		path.pb(it->f);
	}
	sort(ALL(path),[](int a,int b){return qr(a,b)==a;});
	REP(i,1,path.size())Bridge(min(path[i-1],path[i]),max(path[i-1],path[i]));
}
 
void Solve(int n){
	o=rd()%n;
	vector<int>v;
	REP(i,0,n)v.pb(i);
	solve(o,v);
}

Compilation message (stderr)

meetings.cpp: In function 'void solve(int, std::vector<int>)':
meetings.cpp:7:44: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 #define REP(i,j,k) for(register int i=(j);i<(k);++i)
                                            ^
meetings.cpp:32:2: note: in expansion of macro 'REP'
  REP(i,0,v.size())mp[qr(u,v[i])].pb(v[i]);
  ^~~
meetings.cpp:7:44: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 #define REP(i,j,k) for(register int i=(j);i<(k);++i)
                                            ^
meetings.cpp:39:2: note: in expansion of macro 'REP'
  REP(i,1,path.size())Bridge(min(path[i-1],path[i]),max(path[i-1],path[i]));
  ^~~

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