提交记录 10452


用户 题目 状态 得分 用时 内存 语言 代码长度
EntropyIncreaser noi19a. 【NOI2019】回家路线 Accepted 100 28.576 ms 10652 KB C++ 2.42 KB
提交时间 评测时间
2019-09-18 10:56:29 2020-08-01 02:15:50
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cstring>

#include <algorithm>
#include <numeric>
#include <functional>
#include <vector>

#define LOG(FMT...) fprintf(stderr, FMT)

using namespace std;

typedef long long ll;

struct Vec {
  int x, y;
  
  Vec() : x(0), y(0) {}
  Vec(int x, int y) : x(x), y(y) {}
  
  Vec operator+(const Vec& rhs) const { return Vec(x + rhs.x, y + rhs.y); }
  Vec operator-() const { return Vec(-x, -y); }
  Vec operator-(const Vec& rhs) const { return *this + (-rhs); } 
  
  ll operator*(const Vec& rhs) const { return x * (ll)rhs.y - y * (ll)rhs.x; }
  ll operator^(const Vec& rhs) const { return x * (ll)rhs.x + y * (ll)rhs.y; }
};

const int N = 100010, M = 200010, K = 1010;

int n, m, A, B, C; 
int ptr[N];
int x[M], y[M], p[M], q[M], res[M];

vector<int> start[K], dest[K];
vector<Vec> hull[N];

void chkmin(int& x, int y) {
  if (x > y) x = y;
}

int main() {
  freopen("route.in", "r", stdin);
  freopen("route.out", "w", stdout);
  
  // A(t - s)^2 + B(t - s) + C = At^2 + As^2 - 2Ast + Bt - Bs + C
  // = (As^2 - Bs) * 1 + s * -2At + At^2+Bt + C
  // = (Res+As^2-Bs, s)^(1, -2At) + At^2+Bt+C
  
  scanf("%d%d%d%d%d", &n, &m, &A, &B, &C);
  for (int i = 1; i <= m; ++i) {
    scanf("%d%d%d%d", &x[i], &y[i], &p[i], &q[i]);
    start[p[i]].push_back(i);
    dest[q[i]].push_back(i);
  }
  memset(res, -1, sizeof(res));
  int ans = -1;
  hull[1].push_back(Vec(0, 0));
  for (int t = 0; t <= 1000; ++t) {
    for (int i : dest[t]) {
      if (res[i] == -1) continue;
      if (y[i] == n)
        if (ans == -1 || ans > res[i] + t)
          ans = res[i] + t;
      Vec ins(t, res[i] + (A * t - B) * t);
      if (hull[y[i]].empty()) {
        hull[y[i]].push_back(ins);
        continue;
      }
      if (hull[y[i]].back().x == t && hull[y[i]].back().y < ins.y)
        continue;
      int top = (int)hull[y[i]].size() - 1;
      while (top && ((hull[y[i]][top] - hull[y[i]][top - 1]) * (ins - hull[y[i]][top])) <= 0) {
        top--;
        hull[y[i]].pop_back();
      }
      hull[y[i]].push_back(ins);
    }
    for (int i : start[t]) {
      if (hull[x[i]].empty()) continue;
      Vec chk(-2 * A * t, 1);
      ptr[x[i]] = min(ptr[x[i]], (int)hull[x[i]].size() - 1);
      int& p = ptr[x[i]];
      while (p + 1 < hull[x[i]].size() && (chk ^ hull[x[i]][p + 1]) <= (chk ^ hull[x[i]][p]))
        ++p;
      res[i] = (chk ^ hull[x[i]][p]) + (A * t + B) * t + C;
    }
  } 
  printf("%d\n", ans);
  
  return 0;
}

CompilationN/AN/ACompile OKScore: N/A

Testcase #1558.99 us3 MB + 156 KBAcceptedScore: 5

Testcase #2564.95 us3 MB + 156 KBAcceptedScore: 5

Testcase #3565.93 us3 MB + 152 KBAcceptedScore: 5

Testcase #4560.99 us3 MB + 152 KBAcceptedScore: 5

Testcase #51.183 ms3 MB + 292 KBAcceptedScore: 5

Testcase #61.21 ms3 MB + 312 KBAcceptedScore: 5

Testcase #71.205 ms3 MB + 308 KBAcceptedScore: 5

Testcase #81.219 ms3 MB + 320 KBAcceptedScore: 5

Testcase #91.208 ms3 MB + 308 KBAcceptedScore: 5

Testcase #101.045 ms3 MB + 284 KBAcceptedScore: 5

Testcase #111.088 ms3 MB + 292 KBAcceptedScore: 5

Testcase #121.126 ms3 MB + 304 KBAcceptedScore: 5

Testcase #131.103 ms3 MB + 296 KBAcceptedScore: 5

Testcase #141.135 ms3 MB + 304 KBAcceptedScore: 5

Testcase #1525.882 ms9 MB + 1000 KBAcceptedScore: 5

Testcase #1625.569 ms9 MB + 888 KBAcceptedScore: 5

Testcase #1725.603 ms9 MB + 524 KBAcceptedScore: 5

Testcase #1822.255 ms8 MB + 820 KBAcceptedScore: 5

Testcase #1928.576 ms10 MB + 412 KBAcceptedScore: 5

Testcase #2023.951 ms9 MB + 108 KBAcceptedScore: 5


Judge Duck Online | 评测鸭在线
Server Time: 2024-10-05 11:06:07 | Loaded in 2 ms | Server Status
个人娱乐项目,仅供学习交流使用