Submission #261660

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
261660	2020-08-11T23:58:08 Z	tincamatei	Sailing Race (CEOI12_race)	C++14	60 / 100	3000 ms	6472 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 != prev_node(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

60.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	384 KB	Output is correct
2	Correct	1 ms	640 KB	Output is correct
3	Correct	2 ms	768 KB	Output is correct
4	Incorrect	3 ms	768 KB	Output isn't correct
5	Correct	3 ms	896 KB	Output is correct
6	Incorrect	7 ms	1024 KB	Output isn't correct
7	Correct	6 ms	1152 KB	Output is correct
8	Correct	15 ms	1280 KB	Output is 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	2816 KB	Output isn't correct
13	Correct	702 ms	4056 KB	Output is correct
14	Correct	443 ms	5368 KB	Output is correct
15	Execution timed out	3072 ms	6400 KB	Time limit exceeded
16	Execution timed out	3053 ms	6400 KB	Time limit exceeded
17	Execution timed out	3071 ms	6432 KB	Time limit exceeded
18	Correct	819 ms	6472 KB	Output is correct
19	Execution timed out	3069 ms	6400 KB	Time limit exceeded
20	Execution timed out	3064 ms	6400 KB	Time limit exceeded