Submission #261657

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
261657	2020-08-11T23:43:49 Z	tincamatei	Sailing Race (CEOI12_race)	C++14	60 / 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, 2); 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	1 ms	640 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	896 KB	Output isn't correct
5	Correct	2 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	15 ms	1664 KB	Output is correct
11	Correct	13 ms	1536 KB	Output is correct
12	Incorrect	220 ms	2912 KB	Output isn't correct
13	Correct	703 ms	4088 KB	Output is correct
14	Correct	433 ms	5248 KB	Output is correct
15	Execution timed out	3087 ms	6528 KB	Time limit exceeded
16	Execution timed out	3088 ms	6528 KB	Time limit exceeded
17	Execution timed out	3075 ms	6528 KB	Time limit exceeded
18	Correct	813 ms	6516 KB	Output is correct
19	Execution timed out	3084 ms	6528 KB	Time limit exceeded
20	Execution timed out	3091 ms	6528 KB	Time limit exceeded