답안 #946174

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
946174 2024-03-14T11:41:40 Z RedGrey1993 Sailing Race (CEOI12_race) C++17
5 / 100
816 ms 5924 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; }
 
template <unsigned int MOD>
class ModInt {
public:
    ModInt(unsigned long long _v = 0) { set_v((_v % MOD + MOD)); }
    explicit operator bool() const { return val != 0; }
    ModInt operator-() const { return ModInt() - *this; }
    ModInt operator+(const ModInt &r) const { return ModInt().set_v(val + r.val); }
    ModInt operator-(const ModInt &r) const { return ModInt().set_v(val + MOD - r.val); }
    ModInt operator*(const ModInt &r) const { return ModInt().set_v((unsigned int)((unsigned long long)(val)*r.val % MOD)); }
    ModInt operator/(const ModInt &r) const { return *this * r.inv(); }
    ModInt &operator+=(const ModInt &r) { return *this = *this + r; }
    ModInt &operator-=(const ModInt &r) { return *this = *this - r; }
    ModInt &operator*=(const ModInt &r) { return *this = *this * r; }
    ModInt &operator/=(const ModInt &r) { return *this = *this / r; }
    // ModInt &operator=(unsigned long long _v) { set_v((_v % MOD + MOD)); return *this; }
    unsigned int operator=(unsigned long long _v) { set_v((_v % MOD + MOD)); return val; }
    bool operator==(const ModInt &r) const { return val == r.val; }
    bool operator!=(const ModInt &r) const { return val != r.val; }
    ModInt pow(long long n) const {
        ModInt x = *this, r = 1;
        while (n) {
            if (n & 1)
                r *= x;
            x *= x;
            n >>= 1;
        }
        return r;
    }
    ModInt inv() const { return pow(MOD - 2); }
    unsigned int get_val() { return val; }
    friend ostream &operator<<(ostream &os, const ModInt &r) { return os << r.val; }
    friend istream &operator>>(istream &is, ModInt &r) { return is >> r.val; }
private:
    unsigned int val;
    ModInt &set_v(unsigned int _v) {
        val = (_v < MOD) ? _v : _v - MOD;
        return *this;
    }
};
constexpr unsigned int mod = 1e9+7;
using Mint = ModInt<mod>;
 
#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
 
using Mint2 = ModInt<mod-1>;

template <typename T>
struct Line {
  T k, b;
  // 集合中的直线按照斜率从小到大排序,该值表示本直线与下一条直线的交点的横坐标
  mutable T intersect_x;
  bool operator<(const Line<T>& o) const {
    return k < o.k;
  }                            // 用于按照斜率排序
  bool operator<(T x) const {  // 用于在Query时进行二分查找
    return intersect_x < x;
  }                                        // 用于二分查找
  T Eval(T x) const { return k * x + b; }  // 求直线在x点的y值
  T IntersectX(const Line<T>& line) const {  // 求与直线line的交点的横坐标
    assert(k != line.k);  // 斜率不能相等,否则除0异常
    return Div(line.b - b, k - line.k);
  }
  T Div(T a, T b) const {
    if constexpr (std::is_integral<T>::value) {
      // floored division,
      // 因为两条直线之间的交点可能是小数,但是x是整数,因此小数部分永远不会取到
      // 所以求直线交点时只需要记录<=交点横坐标值的最大整数即可
      // 3/2 -> 1; -3/2 -> -2; 4/2 -> 2; -4/2 -> 2
      return a / b - ((a ^ b) < 0 && a % b);
    } else {
      return a / b;
    }
  }
};

template <typename T>
class LichaoTree {
  struct Node {
    Line<T> line{0, numeric_limits<T>::max()};
    int left = -1, right = -1;
  };
 public:
  LichaoTree(T mint, T maxt) {
    mint_ = mint;
    maxt_ = maxt;
  }
  void Add(const Line<T>& line) {
    Add(line, root_, mint_, maxt_);
  }

  T Query(T x) {
    return Query(x, 0, mint_, maxt_);
  }

 private:
  void Add(Line<T> line, int& v, T l, T r) {
    if (v == -1) {
        v = trees.size();
        trees.emplace_back(Node{line, -1, -1});
        return;
    }
    T m = l + (r - l) / 2;
    bool lef = line.Eval(l) < trees[v].line.Eval(l);
    bool mid = line.Eval(m) < trees[v].line.Eval(m);
    bool rht = line.Eval(r) < trees[v].line.Eval(r);
    if (mid) {
      swap(trees[v].line, line);
    }
    if ((lef && rht) || (!lef && !rht)) {
      return;
    } else if (lef != mid) {
      Add(line, trees[v].left, l, m);
    } else {
      Add(line, trees[v].right, m, r);
    }
  }
  T Query(T x, int v, T l, T r) {
    if (v == -1) return numeric_limits<T>::max();
    T m = l + (r - l) / 2;
    if (x < m) {
      return min(trees[v].line.Eval(x), Query(x, trees[v].left, l, m));
    } else {
      return min(trees[v].line.Eval(x), Query(x, trees[v].right, m, r));
    }
  }
  T mint_,maxt_;
  vector<Node> trees;
  int root_ = -1;
};

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] = 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] = 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) {
              rep(j,1,n+1) {
                if (dfs_c(i, j) > ans) {
                  ans = dfs_c(i, j);
                  st = i;
                }
                if (dfs_cc(i, j) > ans) {
                  ans = dfs_cc(i, j);
                  st = i;
                }
              }
            }

            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);
              // dbg(dp_c);
              // dbg(dp_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:278:17: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
  278 |                 if (i > n) i -= n; if (k > n) k-=n;
      |                 ^~
race.cpp:278:36: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
  278 |                 if (i > n) i -= n; if (k > n) k-=n;
      |                                    ^~
race.cpp:290:21: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
  290 |                     if (i > n) i -= n; if (k > n) k-=n;
      |                     ^~
race.cpp:290:40: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
  290 |                     if (i > n) i -= n; if (k > n) k-=n;
      |                                        ^~
race.cpp:300:17: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
  300 |                 if (i < 1) i += n; if (k < 1) k+=n;
      |                 ^~
race.cpp:300:36: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
  300 |                 if (i < 1) i += n; if (k < 1) k+=n;
      |                                    ^~
race.cpp:312:21: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
  312 |                     if (i < 1) i += n; if (k < 1) k+=n;
      |                     ^~
race.cpp:312:40: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
  312 |                     if (i < 1) i += n; if (k < 1) k+=n;
      |                                        ^~
# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 348 KB Output is correct
2 Incorrect 1 ms 348 KB Output isn't correct
3 Incorrect 1 ms 348 KB Output isn't correct
4 Incorrect 1 ms 348 KB Output isn't correct
5 Incorrect 1 ms 348 KB Output isn't correct
6 Incorrect 3 ms 348 KB Output isn't correct
7 Incorrect 4 ms 564 KB Output isn't correct
8 Incorrect 5 ms 604 KB Output isn't correct
9 Incorrect 5 ms 604 KB Output isn't correct
10 Incorrect 14 ms 604 KB Output isn't correct
11 Incorrect 7 ms 604 KB Output isn't correct
12 Incorrect 46 ms 1116 KB Output isn't correct
13 Incorrect 96 ms 2344 KB Output isn't correct
14 Incorrect 63 ms 2396 KB Output isn't correct
15 Incorrect 509 ms 5720 KB Output isn't correct
16 Incorrect 654 ms 5924 KB Output isn't correct
17 Incorrect 550 ms 5508 KB Output isn't correct
18 Incorrect 84 ms 3556 KB Output isn't correct
19 Incorrect 816 ms 5888 KB Output isn't correct
20 Incorrect 807 ms 5680 KB Output isn't correct