Submission #95218

#	Time	Username	Problem	Language	Result	Execution time	Memory
95218		jangwonyoung	Park (JOI17_park)	C++14	67 / 100	160 ms	832 KiB

park

#include "park.h"
#include<iostream>
#include<queue>
using namespace std;
#define pb push_back
//const int N=1401,M=1501;
int n;
vector<int>qry;
//int qar[1501];
vector<int>adj[1501];

vector<int>ds[1501];
int d[1501];
bool in[1501];
int tzuyu(int s,int e){
	int qar[n];
	for(int i=0; i<n ;i++) qar[i]=0;
	for(auto cur:qry) qar[cur]=1;
	if(s>e) swap(s,e);
	int res=Ask(s,e,qar);
	qry.clear();qry.shrink_to_fit();
	return res;
}
void add(int x,int y){
	adj[x].pb(y);adj[y].pb(x);
	Answer(min(x,y),max(x,y));
}
vector<int>g;vector<int>h;
int bs(int s,int e){
	int l=0,r=g.size()-1;
	while(l!=r){
		int mid=(l+r)/2;
		for(auto cur:h) qry.pb(cur);
		for(int i=0; i<=mid ;i++) qry.pb(g[i]);
		int res=tzuyu(s,e);
		if(res) r=mid;
		else l=mid+1;
	}
	int res=g[l];
	g.clear();g.shrink_to_fit();h.clear();h.shrink_to_fit();
	return res;
}
void expand(int x,int y){
	qry.pb(x);qry.pb(y);
	if(tzuyu(x,y)){
		d[y]=d[x]+1;ds[d[y]].pb(y);
		add(x,y);
		return;
	}
	h.pb(x);h.pb(y);
	for(int i=0; i<n ;i++) if(!in[i]) g.pb(i);
	int res=bs(x,y);
	in[res]=true;
	expand(x,res);expand(res,y);
}
void addtotree(int id){
	for(int i=0; i<n ;i++) for(auto cur:ds[i]) g.pb(cur);//bfs order of some kind
	for(int i=0; i<n ;i++) if(!in[i]) h.pb(i);
	int boss=bs(0,id);in[id]=true;
	expand(boss,id);
}
void init(){
	ds[0].pb(0);
	in[0]=true;
}
void Detect(int T, int N){
	n=N;
	init();
	for(int i=1; i<n ;i++){
		if(!in[i]) addtotree(i);
	}
}

• Subtask 1: 0 / 10
• Subtask 2: 10 / 10
• Subtask 3: 27 / 27
• Subtask 4: 30 / 30
• Subtask 5: 0 / 23