oj.uz

답안 #261657

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
261657 2020-08-11T23:43:49 Z tincamatei Sailing Race (CEOI12_race) C++14
60 / 100
 3000 ms 6528 KB 
#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

# 결과 실행 시간 메모리 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