Submission #946174

#TimeUsernameProblemLanguageResultExecution timeMemory
946174RedGrey1993Sailing Race (CEOI12_race)C++17
5 / 100
816 ms5924 KiB
#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 (stderr)

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;
      |                                        ^~
#Verdict Execution timeMemoryGrader output
Fetching results...