답안 #959633

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
959633 2024-04-08T14:40:06 Z RedGrey1993 Sailing Race (CEOI12_race) C++17
100 / 100
833 ms 5892 KB
#include <bits/stdc++.h>
 
using namespace std;
 
template <typename T1, typename T2> istream &operator>>(istream &is, pair<T1, T2> &pa) { is >> pa.first >> pa.second; return is; }
template <typename T> istream &operator>>(istream &is, vector<T> &vec) { for (auto &v : vec) is >> v; return is; }
template <typename T1, typename T2> ostream &operator<<(ostream &os, const pair<T1, T2> &pa) { os << "(" << pa.first << "," << pa.second << ")"; return os; }
template <typename T> ostream &operator<<(ostream &os, const vector<T> &vec) { os << "["; for (auto v : vec) os << v << ","; os << "]"; return os; }
template <typename T> ostream &operator<<(ostream &os, const deque<T> &vec) { os << "deq["; for (auto v : vec) os << v << ","; os << "]"; return os; }
template <typename T> ostream &operator<<(ostream &os, const set<T> &vec) { os << "{"; for (auto v : vec) os << v << ","; os << "}"; return os; }
template <typename T> ostream &operator<<(ostream &os, const multiset<T> &vec) { os << "{"; for (auto v : vec) os << v << ","; os << "}"; return os; }
template <typename T> ostream &operator<<(ostream &os, const unordered_set<T> &vec) { os << "{"; for (auto v : vec) os << v << ","; os << "}"; return os; }
template <typename T> ostream &operator<<(ostream &os, const unordered_multiset<T> &vec) { os << "{"; for (auto v : vec) os << v << ","; os << "}"; return os; }
template <typename TK, typename TV> ostream &operator<<(ostream &os, const unordered_map<TK, TV> &mp) { os << "{"; for (auto v : mp) os << v.first << "=>" << v.second << ","; os << "}"; return os; }
template <typename TK, typename TV> ostream &operator<<(ostream &os, const map<TK, TV> &mp) { os << "{"; for (auto v : mp) os << v.first << "=>" << v.second << ","; os << "}"; return os; }
template <typename T> void resize_array(vector<T> &vec, int len) { vec.resize(len); }
template <typename T, typename... Args> void resize_array(vector<T> &vec, int len, Args... args) { vec.resize(len); for (auto &v : vec) resize_array(v, args...); }
template <typename T1, typename T2> pair<T1, T2> operator+(const pair<T1, T2> &l, const pair<T1, T2> &r) { return make_pair(l.first + r.first, l.second + r.second); }
template <typename T1, typename T2> pair<T1, T2> operator-(const pair<T1, T2> &l, const pair<T1, T2> &r) { return make_pair(l.first - r.first, l.second - r.second); }
long long gcd(long long a, long long b) { return b ? gcd(b, a % b) : a; }
mt19937 mrand(random_device{}());
int rnd(int x) { return mrand() % x; }
 
#define rep(i, a, n) for (int i = a; i < (n); i++)
#define per(i, a, n) for (int i = (n)-1; i >= a; i--)
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(), (x).end()
#define fi first
#define se second
#define sz(x) ((int)(x).size())
typedef vector<int> vi;
typedef long long ll;
typedef unsigned int uint;
typedef unsigned long long ull;
typedef pair<int, int> pii;
typedef double db;
#if DEBUG
#define dbg(x) cerr << #x << " = " << (x) << " (L" << __LINE__ << ") " << __FILE__ << endl;
#else
#define dbg(x)
#endif
 
class Solution {
public:
    void Solve() {
        int n,op;
        while(cin>>n>>op) {
            vector<vi> edges(n+1);
            vector<vi> has_edge(n+1, vi(n+1, 0));
            rep(from,1,n+1) {
                int to;
                while(cin>>to) {
                    if (to == 0) break;
                    edges[from].emplace_back(to);
                    has_edge[from][to] = 1;
                }
            }
            // c -> clockwise, cc -> counter_clockwise
            vector<vi> dp_c(n+1, vi(n+1, -1)), dp_cc(n+1, vi(n+1, -1));
            // is s<k<e ?
            auto between_range = [&] (int k, int s, int e, bool clockwise) {
                if (clockwise) swap(s, e);
                if (s==e) return k!=s;
                int d1 = k-s; if (d1<0) d1 += n;
                int d2 = e-s; if (d2<0) d2 += n;
                return k!=s && d1 < d2;
            };
 
            function<int(int,int)> dfs_c,dfs_cc;
            // [i,j)
            // dp_c[i][j] = 1 + max(dp_c[k][j], dp_cc[k][i])  exists(i->k, j<k<i)
            // dp_cc[i][j] = 1 + max(dp_cc[k][j], dp_c[k][i]) exists(i->k, i<k<j)
            dfs_c = [&] (int i, int j) -> int {
                if (dp_c[i][j] != -1) return dp_c[i][j];
                dp_c[i][j] = 0;
                for (int k : edges[i]) {
                    if (between_range(k, i, j, true)) {
                        dp_c[i][j] = max(dp_c[i][j], 1 + max(dfs_c(k, j), dfs_cc(k, i)));
                    }
                }
                return dp_c[i][j];
            };
 
            dfs_cc = [&] (int i, int j) -> int {
                if (dp_cc[i][j] != -1) return dp_cc[i][j];
                dp_cc[i][j] = 0;
                for (int k : edges[i]) {
                    if (between_range(k, i, j, false)) {
                        dp_cc[i][j] = max(dp_cc[i][j], 1 + max(dfs_cc(k, j), dfs_c(k, i)));
                    }
                }
                return dp_cc[i][j];
            };
 
            int ans = 0, st = 0;
            rep(i,1,n+1) {
              if (dfs_c(i, i) > ans) {
                ans = dfs_c(i, i);
                st = i;
              }
              rep(j,1,n+1) {
                dfs_c(i, j);
                dfs_cc(i, j);
              }
            }
            // dbg(dp_c);
            // dbg(dp_cc);
 
            if (op) {
              vector<vi> dp_succ_c(n+1, vi(n+1, -1)), dp_succ_cc(n+1, vi(n+1, -1));
              function<int(int,int)> dfs_succ_c = [&] (int i, int j) -> int {
                  if (i==j) return dp_succ_c[i][j]=0;
                  if (dp_succ_c[i][j] != -1) return dp_succ_c[i][j];
                  dp_succ_c[i][j] = -2;
                  for (int k : edges[i]) {
                      if ((k==j||between_range(k, i, j, true)) && dfs_succ_c(k, j) >= 0) {
                          dp_succ_c[i][j] = max(dp_succ_c[i][j], 1 + dfs_succ_c(k, j));
                      }
                  }
                  return dp_succ_c[i][j];
              };
              rep(i,1,n+1) {
                rep(j,1,n+1) dfs_succ_c(i,j);
              }
 
              function<int(int,int)> dfs_succ_cc = [&] (int i, int j) -> int {
                  if (i==j) return dp_succ_cc[i][j]=0;
                  if (dp_succ_cc[i][j] != -1) return dp_succ_cc[i][j];
                  dp_succ_cc[i][j] = -2;
                  for (int k : edges[i]) {
                      if ((k==j||between_range(k, i, j, false)) && dfs_succ_cc(k, j) >= 0) {
                          dp_succ_cc[i][j] = max(dp_succ_cc[i][j], 1 + dfs_succ_cc(k, j));
                      }
                  }
                  return dp_succ_cc[i][j];
              };
              rep(i,1,n+1) {
                rep(j,1,n+1) dfs_succ_cc(i,j);
              }
              // dbg(dp_succ_c);
              // dbg(dp_succ_cc);
 
              vi ansv(n+1);
              // ans[i] = max(1+dp_succ_c[j][k]+1+max(dp_c[l][j], dp_cc[l][i])) exists(k->l, j<l<i), dp_succ_c[j][k]!=0
              rep(j,1,n+1) {
                int i = j + 1, k = i + 1;
                if (i > n) i -= n; if (k > n) k-=n;
                while(true) {
                  if (has_edge[i][j]) {
                    if (dp_succ_c[j][k] > 0) {
                      for (int l:edges[k]) {
                        if (between_range(l,i,j,true)) ansv[i] = max(ansv[i], 1+dp_succ_c[j][k]+1+max(dp_c[l][j], dp_cc[l][i]));
                      }
                    }
                    if (has_edge[k][j]) i = k;
                    k++; if (k > n) k-=n;
                  } else {
                    i++; k=i+1;
                    if (i > n) i -= n; if (k > n) k-=n;
                  }
                  if (k==j) break;
                  if (i==j) break;
                }
              }
 
              // ans[i] = max(1+dp_succ_cc[j][k]+1+max(dp_cc[l][j], dp_c[l][i])) exists(k->l, i<l<j), dp_succ_cc[j][k]!=0
              rep(j,1,n+1) {
                int i = j - 1, k = i - 1;
                if (i < 1) i += n; if (k < 1) k+=n;
                while(true) {
                  if (has_edge[i][j]) {
                    if (dp_succ_cc[j][k] > 0) {
                      for (int l:edges[k]) {
                        if (between_range(l,i,j,false)) ansv[i] = max(ansv[i], 1+dp_succ_cc[j][k]+1+max(dp_cc[l][j], dp_c[l][i]));
                      }
                    }
                    if (has_edge[k][j]) i = k;
                    k--; if (k < 1) k+=n;
                  } else {
                    i--; k=i-1;
                    if (i < 1) i += n; if (k < 1) k+=n;
                  }
                  if (k==j) break;
                  if (i==j) break;
                }
              }
 
              // dbg(ansv);
              // ans = 0; st = 0;
              rep(i,1,n+1) if (ansv[i]>ans) {
                ans = ansv[i];
                st = i;
              }
            }
 
            cout << ans << endl;
            cout << st << endl;
        }
    }
private:
};
 
// #define USACO 1
void set_io(const string &name = "") {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
#if FILE_IO || USACO
    if (!name.empty()) {
        freopen((name + ".in").c_str(), "r", stdin);
        freopen((name + ".out").c_str(), "w", stdout);
    }
#endif
}
 
int main() {
#if USACO
    set_io("time");
#else
    set_io("tmp");
#endif
    Solution().Solve();
 
    return 0;
}

Compilation message

race.cpp: In member function 'void Solution::Solve()':
race.cpp:148:17: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
  148 |                 if (i > n) i -= n; if (k > n) k-=n;
      |                 ^~
race.cpp:148:36: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
  148 |                 if (i > n) i -= n; if (k > n) k-=n;
      |                                    ^~
race.cpp:160:21: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
  160 |                     if (i > n) i -= n; if (k > n) k-=n;
      |                     ^~
race.cpp:160:40: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
  160 |                     if (i > n) i -= n; if (k > n) k-=n;
      |                                        ^~
race.cpp:170:17: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
  170 |                 if (i < 1) i += n; if (k < 1) k+=n;
      |                 ^~
race.cpp:170:36: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
  170 |                 if (i < 1) i += n; if (k < 1) k+=n;
      |                                    ^~
race.cpp:182:21: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
  182 |                     if (i < 1) i += n; if (k < 1) k+=n;
      |                     ^~
race.cpp:182:40: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
  182 |                     if (i < 1) i += n; if (k < 1) k+=n;
      |                                        ^~
# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 3 ms 560 KB Output is correct
7 Correct 4 ms 348 KB Output is correct
8 Correct 4 ms 600 KB Output is correct
9 Correct 5 ms 348 KB Output is correct
10 Correct 15 ms 684 KB Output is correct
11 Correct 7 ms 604 KB Output is correct
12 Correct 49 ms 1332 KB Output is correct
13 Correct 89 ms 2344 KB Output is correct
14 Correct 67 ms 2396 KB Output is correct
15 Correct 541 ms 5716 KB Output is correct
16 Correct 718 ms 5844 KB Output is correct
17 Correct 575 ms 5712 KB Output is correct
18 Correct 105 ms 3416 KB Output is correct
19 Correct 789 ms 5676 KB Output is correct
20 Correct 833 ms 5892 KB Output is correct