oj.uz

답안 #261660

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