Submission #168582

#	Time	Username	Problem	Language	Result	Execution time	Memory
168582		arnold518	Sailing Race (CEOI12_race)	C++14	40 / 100	3053 ms	6520 KiB

race

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

const int MAXN = 500;

int N, K;
int adj[MAXN+10][MAXN+10];

int dp[MAXN+10][MAXN+10][5];

int f(int x)
{
	x=(x%N+N)%N;
	if(x==0) x+=N;
	return x;
}

int solve(int l, int r, int s)
{
	int i, j;

	if(l==r) return 0;
	int &ret=dp[l][r][s];
	if(ret!=-1) return ret;
	ret=0;

	if(s==0)
	{
		for(i=f(l+1); i!=f(r+1); i=f(i+1))
		{
			if(!adj[l][i]) continue;
			ret=max(ret, solve(f(l+1), i, 1)+1);
			ret=max(ret, solve(i, r, 0)+1);
		}
	}
	else
	{
		for(i=l; i!=r; i=f(i+1))
		{
			if(!adj[r][i]) continue;
			ret=max(ret, solve(l, i, 1)+1);
			ret=max(ret, solve(i, f(r-1), 0)+1);
		}	
	}

	//printf("%d %d %d : %d\n", l, r, s, ret);
	return ret;
}

int main()
{
	int i, j;
	scanf("%d%d", &N, &K);
	for(i=1; i<=N; i++)
	{
		int t;
		while(1)
		{
			scanf("%d", &t);
			if(t==0) break;
			adj[i][t]=1;
		}
	}

	memset(dp, -1, sizeof(dp));

	pii ans={-1, 0};
	for(i=1; i<=N; i++)
	{
		ans=max(ans, {solve(f(i), f(i-1), 0), i});
	}
	printf("%d\n%d", ans.first, ans.second);
}

Compilation message (stderr)

race.cpp: In function 'int solve(int, int, int)':
race.cpp:24:9: warning: unused variable 'j' [-Wunused-variable]
  int i, j;
         ^
race.cpp: In function 'int main()':
race.cpp:56:9: warning: unused variable 'j' [-Wunused-variable]
  int i, j;
         ^
race.cpp:57:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d", &N, &K);
  ~~~~~^~~~~~~~~~~~~~~~
race.cpp:63:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    scanf("%d", &t);
    ~~~~~^~~~~~~~~~

• Subtask 1: 40 / 100