比赛 4043级2023省选模拟赛8 评测结果 AAAAAAAAAAAAAAAAAAAA
题目名称 Moo Route II 最终得分 100
用户昵称 ムラサメ 运行时间 6.427 s
代码语言 C++ 内存使用 28.24 MiB
提交时间 2023-03-29 21:17:13
显示代码纯文本
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. #define sz 200005
  4. struct site
  5. {
  6. int st, stim, ed, etim;
  7. };
  8. site dld[sz];
  9. int n, m, top;
  10. int wei[sz];
  11. bool vis[sz << 1 | 1];
  12. vector<int> tim[sz], ber[sz], fsl[sz << 1 | 1];
  13. int read();
  14. int haf(int, int);
  15. void dfs(int);
  16. int main()
  17. {
  18. freopen("mooroutetwo.in","r",stdin);
  19. freopen("mooroutetwo.out","w",stdout);
  20. int x, y;
  21. n = read(); m = read();
  22. for (int i = 1; i <= m; ++i)
  23. {
  24. dld[i].st = read();
  25. dld[i].stim = read();
  26. dld[i].ed = read();
  27. dld[i].etim = read();
  28. }
  29. for (int i = 1; i <= n; ++i)
  30. wei[i] = read();
  31. for (int i = 1; i <= m; ++i)
  32. {
  33. tim[dld[i].st].emplace_back(dld[i].stim);
  34. tim[dld[i].ed].emplace_back(dld[i].etim + wei[dld[i].ed]);
  35. }
  36. for (int i = 1; i <= n; ++i)
  37. if (tim[i].size())
  38. {
  39. sort(tim[i].begin(), tim[i].end());
  40. x = 0;
  41. for (int j = 1; j < tim[i].size(); ++j)
  42. if (tim[i][j] != tim[i][x])
  43. tim[i][++x] = tim[i][j];
  44. tim[i].resize(x + 1);
  45. for (int j = 0; j <= x; ++j)
  46. ber[i].emplace_back(++top);
  47. for (int j = 1; j <= x; ++j)
  48. fsl[ber[i][j - 1]].emplace_back(ber[i][j]);
  49. }
  50. for (int i = 1; i <= m; ++i)
  51. {
  52. x = haf(dld[i].st, dld[i].stim);
  53. y = haf(dld[i].ed, dld[i].etim + wei[dld[i].ed]);
  54. fsl[x].emplace_back(y);
  55. }
  56. if (ber[1].size())
  57. dfs(1);
  58. puts("0");
  59. for (int i = 2; i <= n; ++i)
  60. {
  61. x = 1;
  62. for (int j = 0; j < ber[i].size(); ++j)
  63. if (vis[ber[i][j]])
  64. {
  65. printf ("%d\n", tim[i][j] - wei[i]);
  66. x = 0; break;
  67. }
  68. if (x)
  69. puts("-1");
  70. }
  71. return 0;
  72. }
  73.  
  74. int read()
  75. {
  76. int x = 0;
  77. char c = getchar();
  78. while (c < '0') c = getchar();
  79. do {
  80. x = x * 10 + (c & 15);
  81. c = getchar();
  82. }while (c >= '0');
  83. return x;
  84. }
  85.  
  86. int haf(int a, int b)
  87. {
  88. int lf = 0, rt = tim[a].size(), mid;
  89. while (rt > lf + 1)
  90. {
  91. mid = lf + rt >> 1;
  92. if (tim[a][mid] <= b)
  93. lf = mid;
  94. else
  95. rt = mid;
  96. }
  97. return ber[a][lf];
  98. }
  99.  
  100. void dfs(int a)
  101. {
  102. vis[a] = true;
  103. for (int i : fsl[a])
  104. if (!vis[i])
  105. dfs(i);
  106. }