Submission #261659

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
261659	2020-08-11T23:49:44 Z	tincamatei	Sailing Race (CEOI12_race)	C++14	40 / 100	3000 ms	6528 KB

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 asc_path[MAX_N][MAX_N], desc_path[MAX_N][MAX_N];
int first_node[MAX_N][MAX_N], last_node[MAX_N][MAX_N];

int N;
static inline int next_node(int v, int k = 1) { return (v + k) % N; }
static inline int prev_node(int v, int k = 1) { return (v + N - k) % N; }

int main() {
  int 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);
    }

    asc_path[i][i] = desc_path[i][i] = 0;
  }
  
  for(int i = 0; i < N; ++i)
    for(int j = 0; j < N; ++j)
      first_node[i][j] = last_node[i][j] = -1;

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

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

  int best_len = 0, start_path = 0;

  for(int i = 0; i < N; ++i) {
    int ii = prev_node(i);

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

    ii = next_node(i);
    if(desc[i][ii] > best_len) {
      best_len = desc[i][ii];
      start_path = i;
    }
  }
  
  if(K == 1 && N >= 4) {
    for(int k = 0; k < N; ++k) {
      for(int len = 1; len <= N; ++len) {
        for(int i = 0; i < N; ++i) {
          int j = next_node(i, len - 1);
          if(graph[i][k]) {
            first_node[i][j] = i;
            last_node[i][j] = j;
          } else if(len > 1) {
            first_node[i][j] = first_node[next_node(i)][j];
            last_node[i][j] = last_node[i][prev_node(j)];
          } else {
            first_node[i][j] = last_node[i][j] = -1;
          }
        }
      }
      
      for(int i = prev_node(k); i != next_node(k); i = prev_node(i))
        for(int j = next_node(k); j != i; j = next_node(j)) {
          // last_node  -> k -> i -> j -> ()
          int root = last_node[next_node(j)][prev_node(i)];
          if(graph[i][j] && root != -1 && desc_path[k][i] != -1) {
            int path_len = 1 + desc_path[k][i] + 1 +
              std::max(
                asc[j][prev_node(root)],
                desc[j][next_node(k)]
              );
          
            if(path_len > best_len) {
              best_len = path_len;
              start_path = root;
            }
          }

          // first_node -> k -> j -> i
          root = first_node[next_node(j)][prev_node(i)];
          if(graph[j][i] && root != -1 && asc_path[k][j] != -1) {
            int path_len = 1 + asc_path[k][j] + 1 +
              std::max(
                asc[i][prev_node(k)],
                desc[i][next_node(root)]
              );
            
            if(path_len > best_len) {
              best_len = path_len;
              start_path = root;
            }
          }
        }
    }
  }

  printf("%d\n%d", best_len, start_path + 1);

  return 0;
}

Compilation message

race.cpp: In function 'int main()':
race.cpp:17: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:21:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &t);
     ~~~~~^~~~~~~~~~
race.cpp:24:12: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
       scanf("%d", &t);
       ~~~~~^~~~~~~~~~

Subtask #1

40.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	384 KB	Output is correct
2	Incorrect	1 ms	640 KB	Output isn't correct
3	Incorrect	1 ms	768 KB	Output isn't correct
4	Incorrect	3 ms	768 KB	Output isn't correct
5	Correct	2 ms	896 KB	Output is correct
6	Incorrect	7 ms	1152 KB	Output isn't correct
7	Correct	5 ms	1152 KB	Output is correct
8	Incorrect	15 ms	1280 KB	Output isn't correct
9	Correct	10 ms	1408 KB	Output is correct
10	Correct	14 ms	1536 KB	Output is correct
11	Correct	13 ms	1536 KB	Output is correct
12	Incorrect	220 ms	2936 KB	Output isn't correct
13	Incorrect	711 ms	4088 KB	Output isn't correct
14	Correct	439 ms	5368 KB	Output is correct
15	Execution timed out	3095 ms	6400 KB	Time limit exceeded
16	Execution timed out	3092 ms	6400 KB	Time limit exceeded
17	Execution timed out	3092 ms	6528 KB	Time limit exceeded
18	Correct	816 ms	6524 KB	Output is correct
19	Execution timed out	3051 ms	6528 KB	Time limit exceeded
20	Execution timed out	3094 ms	6400 KB	Time limit exceeded