比赛 |
4043级2023省选模拟赛8 |
评测结果 |
AAAAAAAAAAAAAAAAAAAA |
题目名称 |
Moo Route II |
最终得分 |
100 |
用户昵称 |
ムラサメ |
运行时间 |
6.427 s |
代码语言 |
C++ |
内存使用 |
28.24 MiB |
提交时间 |
2023-03-29 21:17:13 |
显示代码纯文本
- #include<bits/stdc++.h>
- using namespace std;
- #define sz 200005
- struct site
- {
- int st, stim, ed, etim;
- };
- site dld[sz];
- int n, m, top;
- int wei[sz];
- bool vis[sz << 1 | 1];
- vector<int> tim[sz], ber[sz], fsl[sz << 1 | 1];
- int read();
- int haf(int, int);
- void dfs(int);
- int main()
- {
- freopen("mooroutetwo.in","r",stdin);
- freopen("mooroutetwo.out","w",stdout);
- int x, y;
- n = read(); m = read();
- for (int i = 1; i <= m; ++i)
- {
- dld[i].st = read();
- dld[i].stim = read();
- dld[i].ed = read();
- dld[i].etim = read();
- }
- for (int i = 1; i <= n; ++i)
- wei[i] = read();
- for (int i = 1; i <= m; ++i)
- {
- tim[dld[i].st].emplace_back(dld[i].stim);
- tim[dld[i].ed].emplace_back(dld[i].etim + wei[dld[i].ed]);
- }
- for (int i = 1; i <= n; ++i)
- if (tim[i].size())
- {
- sort(tim[i].begin(), tim[i].end());
- x = 0;
- for (int j = 1; j < tim[i].size(); ++j)
- if (tim[i][j] != tim[i][x])
- tim[i][++x] = tim[i][j];
- tim[i].resize(x + 1);
- for (int j = 0; j <= x; ++j)
- ber[i].emplace_back(++top);
- for (int j = 1; j <= x; ++j)
- fsl[ber[i][j - 1]].emplace_back(ber[i][j]);
- }
- for (int i = 1; i <= m; ++i)
- {
- x = haf(dld[i].st, dld[i].stim);
- y = haf(dld[i].ed, dld[i].etim + wei[dld[i].ed]);
- fsl[x].emplace_back(y);
- }
- if (ber[1].size())
- dfs(1);
- puts("0");
- for (int i = 2; i <= n; ++i)
- {
- x = 1;
- for (int j = 0; j < ber[i].size(); ++j)
- if (vis[ber[i][j]])
- {
- printf ("%d\n", tim[i][j] - wei[i]);
- x = 0; break;
- }
- if (x)
- puts("-1");
- }
- return 0;
- }
-
- int read()
- {
- int x = 0;
- char c = getchar();
- while (c < '0') c = getchar();
- do {
- x = x * 10 + (c & 15);
- c = getchar();
- }while (c >= '0');
- return x;
- }
-
- int haf(int a, int b)
- {
- int lf = 0, rt = tim[a].size(), mid;
- while (rt > lf + 1)
- {
- mid = lf + rt >> 1;
- if (tim[a][mid] <= b)
- lf = mid;
- else
- rt = mid;
- }
- return ber[a][lf];
- }
-
- void dfs(int a)
- {
- vis[a] = true;
- for (int i : fsl[a])
- if (!vis[i])
- dfs(i);
- }