Submission #1204084

#	Time	Username	Problem	Language	Result	Execution time	Memory
1204084		Muhammad_Aneeq	Park (JOI17_park)	C++20	10 / 100	147 ms	32840 KiB

park

#include "park.h"
#include <vector>
#include <map>
#include <iostream>
using namespace std;	
static int Place[1400];
int Deg[1400]={};
int query(int u,int v)
{
	Place[u]=Place[v]=1;
	if (u>v)
		swap(u,v);
	int z=Ask(u,v,Place);
	Place[u]=Place[v]=0;
	return z;
}
map<int,int>vis;
int n;
map<pair<int,int>,bool>done,ed;
int sg(int u,int v)
{
	if (u>v)
		swap(u,v);
	if (ed.find({u,v})==ed.end())
		ed[{u,v}]=query(u,v);
	return ed[{u,v}];
}
void rec(int u,int v)
{
	if (vis[v])
		return;
	if (sg(u,v))
	{
		vis[v]=1;
		if (u>v)
			swap(u,v);
		if (done[{u,v}]) return;
		done[{u,v}]=1;
		Deg[u]++;
		Deg[v]++;
		Answer(u,v);return;
	}
	vector<int>nodes;
	for (int i=0;i<n;i++)
	{
		if (i==u||i==v||Deg[i]==7) continue;
		nodes.push_back(i);
	}
	if (nodes.size()==0)
	{
		Answer(min(u,v),max(u,v));return;
	}
	int st=-1,en=nodes.size()-1;
	while (st+1<en)
	{
		int mid=(st+en)/2;
		for (int i=0;i<=mid;i++)
			Place[nodes[i]]=1;
		if (query(u,v))
			en=mid;
		else
			st=mid;
		for (int i=0;i<=mid;i++)
			Place[nodes[i]]=0;
	}
	rec(u,nodes[en]);rec(nodes[en],v);
}
void Detect(int T, int N) 
{
	n=N;
	if (N==2)
	{
		Answer(0,1);return;
	}
	for (int i=0;i<N;i++)
		Deg[i]=0;
	for (int i=1;i<N;i++)
		rec(0,i);
}

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