Submission #299882

# Submission time Handle Problem Language Result Execution time Memory
299882 2020-09-15T23:04:36 Z YJU Meetings (JOI19_meetings) C++14
0 / 100
70 ms 1272 KB
#include<bits/stdc++.h>
#include "meetings.h"
using namespace std;
typedef int ll;
typedef pair<ll,ll> pll;
typedef long double ld;
const ll MOD=1e9+7;
const ll N=2e3+5;
const ld pi=3.14159265359;
#define REP(i,n) for(ll i=0;i<n;i++)
#define REP1(i,n) for(ll i=1;i<=n;i++)
#define pb push_back
#define mp make_pair
#define X first
#define Y second
#define setp setprecision
#define lwb lower_bound
#define SZ(a) (ll)a.size()

vector<pll> ed;
vector<ll> dg[N];

void build(ll nl,ll nr,vector<ll> &v){
	vector<ll> l,r,midr,midl,line;
	ll id=N-1;
	for(ll i:v){
		ll x=Query(nl,nr,i);
		if(x==nl){
			l.pb(x);
		}else if(x==nr){
			r.pb(x);
		}else{
			if(x==i)line.pb(i);
			dg[x].pb(i);
			id=(SZ(dg[x])>SZ(dg[id])?x:id);
		}
	}
	assert(id==N-1);
	if(SZ(line)==0){ed.pb(mp(nl,nr));}
	for(ll i:line){
		if(i==id)continue;
		ll x=Query(nl,id,i);
		if(x==i){
			for(ll j:dg[i])midl.pb(j);
		}else{
			for(ll j:dg[i])midr.pb(j);
		}
	}
	for(ll i:line)dg[i].clear();
	random_shuffle(l.begin(),l.end());
	random_shuffle(r.begin(),r.end());
	ll ndl=(SZ(l)?l[0]:-1),ndr=(SZ(r)?r[0]:-1);
	if(SZ(r))r.erase(r.begin());
	if(SZ(l))l.erase(l.begin());
	if(ndl!=-1)build(ndl,nl,l);
	if(ndr!=-1)build(ndr,nr,r);
	if(SZ(line))build(nl,id,midl),build(id,nr,midr);
	return ;
}

void Solve(ll n){
	srand(clock());
	vector<ll> v;
	for(int i=2;i<n;i++)v.pb(i);
	build(0,1,v);
	for(auto i:ed){
		if(i.X>i.Y)swap(i.X,i.Y);
		Bridge(i.X,i.Y);
	}
}


# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 384 KB Wrong Answer [3]
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 384 KB Wrong Answer [3]
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 384 KB Wrong Answer [3]
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Runtime error 70 ms 1272 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -