Submission #261555

#	Time	Username	Problem	Language	Result	Execution time	Memory
261555		tincamatei	Sailing Race (CEOI12_race)	C++14	40 / 100	1074 ms	2680 KiB

race

#include <bits/stdc++.h>

const int MAX_N = 500;

bool graph[MAX_N][MAX_N];
int asc[MAX_N][MAX_N], desc[MAX_N][MAX_N];

int main() {
  int N, K;

  scanf("%d%d", &N, &K);

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

  for(int len = 2; len <= N; ++len) {
    for(int i = 0; i < N; ++i) {
      int j = (i + len - 1) % N, k = i;
      
      do {
        k = (k + 1) % N;
        if(graph[i][k])
          asc[i][j] = std::max(asc[i][j], 1 + std::max(asc[k][j], desc[k][(i + 1) % N]));
      } while(k != j);

      j = (i + N - len + 1) % N;
      k = i;

      do {
        k = (k + N - 1) % N;
        if(graph[i][k])
          desc[i][j] = std::max(desc[i][j], 1 + std::max(desc[k][j], asc[k][(i - 1 + N) % N]));
      } while(k != j);
    }
  }

  int best_len = 0, start_path = 0;

  for(int i = 0; i < N; ++i) {
    int ii = ((i + N - 1) % N);

    if(asc[i][ii] > best_len) {
      best_len = asc[i][ii];
      start_path = i;
    }

    ii = (i + 1) % N;
    if(desc[i][ii] > best_len) {
      best_len = desc[i][ii];
      start_path = i;
    }
  }

  printf("%d\n%d", best_len, start_path + 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:15:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &t);
     ~~~~~^~~~~~~~~~
race.cpp:18:12: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
       scanf("%d", &t);
       ~~~~~^~~~~~~~~~

• Subtask 1: 40 / 100