Submission #99337

#	Time	Username	Problem	Language	Result	Execution time	Memory
99337		TadijaSebez	Park (JOI17_park)	C++11	100 / 100	445 ms	760 KiB

park

#include "park.h"
#include <bits/stdc++.h>
using namespace std;
const int N=1405;
const int M=3050;
static int pl[1400];
int use[N],n;
int query(int u, int v)
{
	if(u>v) swap(u,v);
	for(int i=0;i<n;i++) pl[i]=use[i];
	return Ask(u,v,pl);
}
int fir[N],nxt[M],tot,nod[M];
void Add(int u, int v){ tot++;nxt[tot]=fir[u];fir[u]=tot;nod[tot]=v;}
void AddEdge(int u, int v)
{
	if(u>v) swap(u,v);
	Answer(u,v);
	Add(u,v);
	Add(v,u);
}
int col[N];
int all(int x, int y)
{
	for(int i=0;i<n;i++) use[i]=col[i]==1;
	use[x]=use[y]=1;
	return query(x,y);
}
int Get(int x, int y)
{
	int top=n-1,bot=0,mid,ans;
	while(top>=bot)
	{
		mid=top+bot>>1;
		for(int i=0;i<=mid;i++) use[i]=col[i]!=2;
		for(int i=mid+1;i<n;i++) use[i]=col[i]==1;
		use[x]=use[y]=1;
		if(query(x,y)) ans=mid,top=mid-1;
		else bot=mid+1;
	}
	return ans;
}
int was[N];
void Del(int y)
{
	was[y]=0;
	for(int i=fir[y];i;i=nxt[i]) if(was[nod[i]]) Del(nod[i]);
}
int in[N];
vector<int> nodes;
void DFS(int y)
{
	nodes.push_back(y);in[y]=1;
	for(int i=fir[y];i;i=nxt[i]) if(!in[nod[i]] && was[nod[i]]) DFS(nod[i]);
}
void Edge(int x)
{
	for(int i=0;i<n;i++) was[i]=col[i]==1;
	for(int y=0;y<n;y++)
	{
		if(!was[y]) continue;
		for(int i=0;i<n;i++) use[i]=was[i];
		use[x]=use[y]=1;
		if(!query(x,y)){ Del(y);continue;}
		for(int i=0;i<n;i++) in[i]=0;
		nodes.clear();
		DFS(y);
		int top=(int)nodes.size()-1,bot=0,mid,ans;
		while(top>=bot)
		{
			mid=top+bot>>1;
			for(int i=0;i<n;i++) use[i]=0;
			for(int i=0;i<=mid;i++) use[nodes[i]]=1;
			use[x]=use[y]=1;
			if(query(x,y)) ans=nodes[mid],top=mid-1;
			else bot=mid+1;
		}
		AddEdge(x,ans);
		was[ans]=0;
		y--;
	}
}
void Work(int x)
{
	col[x]=2;
	while(!all(0,x)) Work(Get(0,x));
	Edge(x);
	col[x]=1;
}
void Detect(int T, int N)
{
	n=N;col[0]=1;
	for(int i=1;i<n;i++) if(!col[i]) Work(i);
}

Compilation message (stderr)

park.cpp: In function 'int Get(int, int)':
park.cpp:35:10: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   mid=top+bot>>1;
       ~~~^~~~
park.cpp: In function 'void Edge(int)':
park.cpp:72:11: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
    mid=top+bot>>1;
        ~~~^~~~
park.cpp: In function 'int Get(int, int)':
park.cpp:42:9: warning: 'ans' may be used uninitialized in this function [-Wmaybe-uninitialized]
  return ans;
         ^~~
park.cpp: In function 'void Edge(int)':
park.cpp:80:11: warning: 'ans' may be used uninitialized in this function [-Wmaybe-uninitialized]
   was[ans]=0;
   ~~~~~~~~^~

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