首页 > 其他分享 >LOJ #3490. 「JOISC 2021 Day2」逃跑路线

LOJ #3490. 「JOISC 2021 Day2」逃跑路线

时间：2024-09-18 21:35:40浏览次数：1  
标签：std dis1 dis2 le LOJ Day2 3490 int kMaxN

Description

在 IOI 王国，人们使用 Byou 作为时间单位。IOI 王国中的一天被分为了 \(S\) 个时间单位。每天从最开始经过 \(x\ (0 \le x < S)\) Byou 后的时间称为时刻 \(x\)。

IOI 王国由 \(N\) 个城市组成，以 \(0\) 到 \(N-1\) 编号。其中有 \(M\) 条双向道路连接某些城市，以 \(0\) 到 \(M-1\) 编号。你可以通过这些道路从一个城市到达另一个城市。第 \(i\ (0 \le i \le M-1)\) 条道路连接城市 \(A_i\) 和 \(B_i\)，且经过这条道路需要 \(L_i\) Byou。

在每天，人们会在道路 \(i\) 进行一次严格的安检，并从时刻 \(C_i\) 持续到当天结束。

JOI 帮是 IOI 王国的一个秘密组织。由于其神秘性，JOI 帮的成员构成是高度机密。这意味着其中的成员不能遭遇任何一次安检。因此，如果 JOI 帮的成员需要经过道路 \(i\)，TA 从 \(A_i\) 或 \(B_i\) 起身出发的时刻 \(x\) 必须满足 \(0 \le x \le C_i - L_i\)。由于安检并非在城市内进行，而是在路上，所以 JOI 帮的成员可以在道路 \(i\) 安检时出现在城市 \(A_i\) 或 \(B_i\)。

JOI 帮有 \(Q\) 个成员，以 \(0\) 到 \(Q-1\) 编号。成员 \(j\ (0 \le j \le Q-1)\) 会在某天的时刻 \(T_j\) 从城市 \(U_j\) 出发前往城市 \(V_j\)。成员们可以在途中的某个城市里小憩一会。成员 \(j\) 可能需要很多天才能到达城市 \(V_j\)。

请您编写一个程序，对于给定的城市、道路、安检和 JOI 帮的成员的信息，对于每个 \(j\ (0 \le j \le Q-1)\) 计算出成员 \(j\) 从 \(U_j\) 到达 \(V_j\) 的最少时间。

  • \(2 \le N \le 90\)。
  • \(N-1 \le M \le \frac{N(N-1)}2\)。
  • \(2 \le S \le 10^{15}\)。
  • \(1 \le Q \le 3\times 10^5\)。
  • \(0 \le A_i \le N-1\ (0 \le i \le M-1)\)。
  • \(0 \le B_i \le N-1\ (0 \le i \le M-1)\)。
  • \(A_i \ne B_i\ (0 \le i \le M-1)\)。
  • \((A_i,B_i) \ne (A_k,B_k),(A_i,B_i) \ne (B_k,A_k)\ (0 \le i < k \le M-1)\)。
  • \(1 \le L_i <S\ (0 \le i \le M-1)\)。
  • \(L_i \le C_i <S\ (0 \le i \le M-1)\)。
  • 您可以通过城市之间的某些道路从任意城市到达任意其他城市。
  • \(0 \le U_j \le N-1\ (0 \le j \le Q-1)\)。
  • \(0 \le V_j \le N-1\ (0 \le j \le Q-1)\)。
  • \(U_j \ne V_j\ (0 \le j \le Q-1)\)。
  • \(0 \le T_j < S\ (0 \le j \le Q-1)\)。

Solution

首先有个单次询问 \(O(n^2+m)\) 的做法是直接暴力跑 dijkstra 最短路。显然过不了。

考虑优化。

刚才那个做法主要慢在没有任何预处理而每次重新做询问，导致询问时间复杂度过高而超时。注意到当一个点第一次被道路卡后，时间\(\bmod S\) 一定为 \(0\)，这样起点的状态只有 \(O(n)\) 种，可以预处理了。

根据上面那个做法可以将答案路径分为两种：在一天内走完、走至少两天。

先考虑第一种情况，对于第二种情况可以枚举第一天走的最后的点，就转化为了第一天和初始时间为 \(0\) 的情况了。

同样是预处理。固定起点和终点，对于一组方案，设 \((u,v,l,c)\) 为方案中经过的边，\(x\) 为到 \(u\) 的时间，将初始时间往后移 \([0,c-l-x]\) 这条边仍然能走，所以每次找到 \(c-l-x\) 最小的边删掉，在剩下的边继续跑即可预处理出所有初始时间区间的答案。时间复杂度：\(O(n^5)\)，过不了。

显然可以枚举瓶颈边 \((u,v,l,c)\)，则到 \(u\) 的时间小于等于 \(c-l\)，\(v\) 当天到后面点的时间等于 \(c\) 时刻从 \(v\) 出发的时间。所以可以设 \(dis1_x\) 表示当天从 \(x\) 到 \(u\) 的最小时间，通过这个东西可以求出 \((u,v,l,c)\) 为瓶颈边的最大初始时刻。\(dis2_x\) 表示当天 \(c\) 时刻从 \(v\) 到 \(x\) 的最小时间。于是 \(x\to y\) 的路径中瓶颈边为 \((u,v,l,c)\) 最小时间为 \(dis1_x+dis2_y+l\)。

然后搞个 vector 维护每对起点和终点经过所有瓶颈边对应的最小时间，先按照初始时间的限制排序，查询时二分出可行的后缀即可。

如果至少走两天，可以设 \(f_{x,y}\) 表示当天从 \(y\) 到 \(x\) 的最小时间，\(g_{x,y}\) 表示 \(0\) 时刻从 \(x\) 到 \(y\) 的最小时间，这两个数组的求法和上面瓶颈边的 \(dis1,dis2\) 差不多，然后枚举中转点 \(i\)，贡献即为 \(\min\limits_{s-f_{u,i}\geq t}{s+g_{v,i}-t}\)。

时间复杂度：\(O(n^4+qn+q\log n)\)。

具体细节见代码。

Code

#include <bits/stdc++.h>

// #define int int64_t

namespace FASTIO {
char ibuf[1 << 21], *p1 = ibuf, *p2 = ibuf;
char getc() {
  return p1 == p2 && (p2 = (p1 = ibuf) + fread(ibuf, 1, 1 << 21, stdin), p1 == p2) ? EOF : *p1++;
}
template<class T> bool read(T &x) {
  x = 0; int f = 0; char ch = getc();
  while (ch < '0' || ch > '9') f |= ch == '-', ch = getc();
  while (ch >= '0' && ch <= '9') x = (x * 10) + (ch ^ 48), ch = getc();
  x = (f ? -x : x); return 1;
}
template<typename A, typename ...B> bool read(A &x, B &...y) { return read(x) && read(y...); }
 
char obuf[1 << 21], *o1 = obuf, *o2 = obuf + (1 << 21) - 1;
void flush() { fwrite(obuf, 1, o1 - obuf, stdout), o1 = obuf; }
void putc(char x) { *o1++ = x; if (o1 == o2) flush(); }
template<class T> void write(T x) {
  if (!x) putc('0');
  if (x < 0) x = -x, putc('-');
  char c[40]; int tot = 0;
  while (x) c[++tot] = x % 10, x /= 10;
  for (int i = tot; i; --i) putc(c[i] + '0');
}
void write(char x) { putc(x); }
void write(char *x) { while (*x) putc(*x++); }
void write(const char *x) { while (*x) putc(*x++); }
template<typename A, typename ...B> void write(A x, B ...y) { write(x), write(y...); }
struct Flusher {
  ~Flusher() { flush(); }
} flusher;
} // namespace FASTIO
using FASTIO::read; using FASTIO::putc; using FASTIO::write;

const int kMaxN = 95, kMaxM = kMaxN * kMaxN / 2;
const int64_t kInf = 1e18;

int n, m, q;
int u[kMaxM], v[kMaxM];
int64_t s, l[kMaxM], c[kMaxM], f[kMaxN][kMaxN], g[kMaxN][kMaxN], dis1[kMaxN], dis2[kMaxN];
std::vector<std::tuple<int, int64_t, int64_t>> G[kMaxN];
std::vector<std::pair<int64_t, int64_t>> vec[kMaxN][kMaxN];

void dijkstra1(int x, int64_t t) {
  static bool vis[kMaxN];
  for (int i = 1; i <= n; ++i) {
    dis1[i] = kInf, vis[i] = 0;
  }
  std::queue<int> q;
  q.emplace(x), dis1[x] = 0;
  for (int c = 1; c <= n; ++c) {
    int u = 0;
    for (int i = 1; i <= n; ++i)
      if (!vis[i] && (!u || dis1[i] < dis1[u]))
        u = i;
    if (!u || dis1[u] >= 1e17) break;
    vis[u] = 1;
    for (auto [v, l, c] : G[u]) {
      if (t - dis1[u] - l < 0) continue;
      if (t - dis1[u] <= c) dis1[v] = std::min(dis1[v], dis1[u] + l);
    }
  }
}

void dijkstra2(int x, int64_t t) {
  static bool vis[kMaxN];
  for (int i = 1; i <= n; ++i) {
    dis2[i] = kInf, vis[i] = 0;
  }
  std::queue<int> q;
  q.emplace(x), dis2[x] = 0;
  for (int c = 1; c <= n; ++c) {
    int u = 0;
    for (int i = 1; i <= n; ++i)
      if (!vis[i] && (!u || dis2[i] < dis2[u]))
        u = i;
    if (!u || dis2[u] >= 1e17) break;
    vis[u] = 1;
    for (auto [v, l, c] : G[u]) {
      int64_t val = dis2[u] + t;
      if (val % s <= c - l) dis2[v] = std::min(dis2[v], dis2[u] + l);
    }
  }
} 

void dijkstra3(int x, int64_t t) {
  static bool vis[kMaxN];
  for (int i = 1; i <= n; ++i) {
    dis1[i] = kInf, vis[i] = 0;
  }
  std::queue<int> q;
  q.emplace(x), dis1[x] = 0;
  for (int c = 1; c <= n; ++c) {
    int u = 0;
    for (int i = 1; i <= n; ++i)
      if (!vis[i] && (!u || dis1[i] < dis1[u]))
        u = i;
    if (!u || dis1[u] >= 1e17) break;
    vis[u] = 1;
    for (auto [v, l, c] : G[u]) {
      if (t - dis1[u] - l < 0) continue;
      if (t - dis1[u] > c) dis1[v] = std::min(dis1[v], dis1[u] + t - dis1[u] - c + l);
      else dis1[v] = std::min(dis1[v], dis1[u] + l);
    }
  }
}

void dijkstra4(int x, int64_t t) {
  static bool vis[kMaxN];
  for (int i = 1; i <= n; ++i) {
    dis2[i] = kInf, vis[i] = 0;
  }
  std::queue<int> q;
  q.emplace(x), dis2[x] = 0;
  for (int c = 1; c <= n; ++c) {
    int u = 0;
    for (int i = 1; i <= n; ++i)
      if (!vis[i] && (!u || dis2[i] < dis2[u]))
        u = i;
    if (!u || dis2[u] >= 1e17) break;
    vis[u] = 1;
    for (auto [v, l, c] : G[u]) {
      int64_t val = dis2[u] + t;
      if (val % s > c - l) val += s - val % s;
      dis2[v] = std::min(dis2[v], val - t + l);
    }
  }
}

int64_t solve(int u, int v, int64_t t) {
  int64_t res = kInf;
  auto it = std::lower_bound(vec[u][v].begin(), vec[u][v].end(), std::pair<int64_t, int64_t>{t, 0});
  if (it != vec[u][v].end()) res = std::min(res, it->second);
  for (int i = 1; i <= n; ++i) {
    if (s - f[i][u] >= t) res = std::min(res, s + g[i][v] - t);
  }
  return res;
}

void dickdreamer() {
  read(n, m, s, q);
  for (int i = 1; i <= m; ++i) {
    read(u[i], v[i], l[i], c[i]);
    ++u[i], ++v[i];
    G[u[i]].emplace_back(v[i], l[i], c[i]), G[v[i]].emplace_back(u[i], l[i], c[i]);
  }
  for (int i = 1; i <= m; ++i) {
    dijkstra1(u[i], c[i] - l[i]), dijkstra2(v[i], c[i]);
    for (int j = 1; j <= n; ++j) {
      for (int k = 1; k <= n; ++k) {
        vec[j][k].emplace_back(c[i] - l[i] - dis1[j], dis1[j] + dis2[k] + l[i]);
      }
    }

    dijkstra1(v[i], c[i] - l[i]), dijkstra2(u[i], c[i]);
    for (int j = 1; j <= n; ++j) {
      for (int k = 1; k <= n; ++k) {
        vec[j][k].emplace_back(c[i] - l[i] - dis1[j], dis1[j] + dis2[k] + l[i]);
      }
    }
  }
  
  for (int i = 1; i <= n; ++i) {
    for (int j = 1; j <= n; ++j) {
      std::sort(vec[i][j].begin(), vec[i][j].end());
      for (int k = (int)vec[i][j].size() - 2; k >= 0; --k) {
        vec[i][j][k].second = std::min(vec[i][j][k].second, vec[i][j][k + 1].second);
      }
    }
  }
  for (int i = 1; i <= n; ++i) {
    dijkstra3(i, s), dijkstra4(i, 0);
    for (int j = 1; j <= n; ++j) {
      f[i][j] = dis1[j], g[i][j] = dis2[j];
    }
  }
  for (int c = 1; c <= q; ++c) {
    int u, v; int64_t t;
    read(u, v, t);
    ++u, ++v;
    write(solve(u, v, t), '\n');
  }
}

int32_t main() {
#ifdef ORZXKR
  freopen("in.txt", "r", stdin);
  freopen("out.txt", "w", stdout);
#endif
  int T = 1;
  // std::cin >> T;
  while (T--) dickdreamer();
  // std::cerr << 1.0 * clock() / CLOCKS_PER_SEC << "s\n";
  return 0;
}

标签：std,dis1,dis2,le,LOJ,Day2,3490,int,kMaxN
From： https://www.cnblogs.com/Scarab/p/18419371

相关文章

  • Day22笔记-多态&函数重写&运算符重载&对象的内置内容
    一、多态多态的前提：继承体现1：同一种事物的多种体现形式，如：动物有很多种体现2：在定义的过程无法确定变量的类型，只有当程序正常运行的时候才会确定该变量是什么类型，调用哪个函数#体现1：同一种事物的多种体现形式，如：动物有很多种classAnimal():  passclassCat(Animal):......
  • Day23笔记-Day21和Day22作业讲解&单例类
    Day22作业讲解'''学生类Student:属性:学号，姓名，年龄，性别，成绩​班级类Grade:属性:班级名称，班级中的学生【使用列表存储学生】​方法:1.查看该班级中的所有学生的信息2.查看指定学号的学生信息3.查看......
  • java_day2_常量，变量，数据类型，运算符
    一、常量常量：在Java程序运行过程中其值不能发生改变的量分类：1、字面值常量：整数常量表示所有的整数，包括负数10-8小数常量表示所有的小数1.23-3.14布尔常量truefalse空常量null......
  • 代码随想录Day2 | LeetCode 209. 长度最小的子数组、LeetCode 59. 螺旋矩阵 II、KamaC
    LeetCode209.长度最小的子数组子数组是一个连续的，很容易想到滑动窗口classSolution:defminSubArrayLen(self,target:int,nums:List[int])->int:windowSum=0left,right=0,0res=float('inf')whileright<len(nums......
  • leetcode刷题day20|二叉树Part08（669. 修剪二叉搜索树、108.将有序数组转换为二叉搜索
    669.修剪二叉搜索树思路：理解了删除二叉搜索树中的节点，这个题理解起来就不难了。还是选用中序遍历递归。递归三步曲：1、传入参数：根节点，最小值，最大值；返回值为根节点；2、终止条件：如果节点为空，直接返回空；3、递归逻辑：如果最小值小于该节点，递归调用该节点的右孩子（检查右孩子......
  • Day20笔记-面向对象&类和对象&类中的属性和函数&构造和析构函数
    一、面向对象基础1.概念1.1面向对象的设计思想面向对象是基于万物皆对象这个哲学观点，在Python中，一切皆对象举例说明：​案例一：我想要吃大盘鸡​面向过程面向对象​1.自己去买菜1.委托一个会砍价的人帮忙去买菜​2.自己择菜2.委托一个临时工帮忙择菜​3.自己......
  • Day21笔记-封装&继承
    复习面向对象基础语法#定义类classPerson():  #类属性  num=10  #限制对象属性的动态绑定  __slots__=('name','age','hobby')  #定义实例属性  def__init__(self,name,age,hobby):    self.name=name    self......
  • Java知识了解Day2
    Java知识了解Day22024年7月2日11:40:17时间有限，了解一小部分知识Java是半解释半编译型语言，半动态半静态。一、变量基本数据类型和运算符1.变量变量就是存储数据的*“房间”*，通过变量名、变量类型来区分内存中不同的数据。插写一点有关编写程序的想法，上课讲到......
  • LOJ#2885. 「SDOI2010」猪国杀
    对拍器在此。https://www.luogu.com/discuss/81283献忠！AC代码modoiread{usestd::{io::{stdin,Read},ops::{Add,Mul,Neg},};pubfnnext()->u8{letmuta=stdin().lock();letmutc=[0u8];matcha......
  • 重拾java-------day2(下载，特点，运行过程，环境变量)
    java背景前言一、java背景二、特点虚拟机jvm（跨平台）jvm,jre,jdkjava程序的运行过程环境变量的配置前言“我曾经喜欢过你，但可惜我先成了大人……”加油！少年一、java背景由SUN公司开发，意思是盛产咖啡的爪哇岛由oracle公司收购，意味着要去oracle公司官网下载二、......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99