Submission #260164

#	Time	Username	Problem	Language	Result	Execution time	Memory
260164		tincamatei	Sailing Race (CEOI12_race)	C++14	0 / 100	176 ms	2560 KiB

race

#include <bits/stdc++.h>

const int MAX_N = 500;
bool graph[MAX_N][MAX_N];

int dp[2][MAX_N][MAX_N];

int main() {
  int N, K;

  scanf("%d%d", &N, &K);
  for(int i = 0; i < N; ++i) {
    int neigh;
    scanf("%d", &neigh);
    while(neigh != 0) {
      graph[i][neigh - 1] = true;
      scanf("%d", &neigh);
    }
  }

  for(int len = 1; len <= N; ++len) {
    for(int i = 0; i < N; ++i) {
      int j = (i + len - 1 + N) % N;
      if(!graph[i][j])
        dp[0][i][j] = 0;
      else {
        int k = (i + 1) % N;
        while(k != j) {
          if(graph[j][k])
            dp[0][i][j] = std::max(dp[1][k][j] + 1, dp[0][i][k] + 1);
          k = (k + 1) % N;
        }
      }
      
      if(!graph[j][i])
        dp[1][i][j] = 0;
      else {
        int k = (j + 1) % N;
        while(k != i) {
          if(graph[i][k])
            dp[1][i][j] = std::max(dp[0][i][k] + 1, dp[1][k][j] + 1);
          k = (k + 1) % N;
        }
      }
    }
  }
  
  int best_len = 0, first_city = -1;

  for(int i = 0; i < N; ++i)
    for(int j = 0; j < N; ++j) {
      if(dp[0][i][j] > best_len) {
        best_len = dp[0][i][j];
        first_city = i;
      }
      if(dp[1][i][j] > best_len) {
        best_len = dp[1][i][j];
        first_city = j;
      }
    }
  printf("%d\n%d", best_len, first_city + 1);
  return 0;
}

Compilation message (stderr)

race.cpp: In function 'int main()':
race.cpp:11:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d", &N, &K);
   ~~~~~^~~~~~~~~~~~~~~~
race.cpp:14:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &neigh);
     ~~~~~^~~~~~~~~~~~~~
race.cpp:17:12: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
       scanf("%d", &neigh);
       ~~~~~^~~~~~~~~~~~~~

• Subtask 1: 0 / 100