CSP-S模拟赛28
| T1 | T2 | T3 | T4 |
|---|---|---|---|
| 100 AC | 25 TLE | 20 TLE | 15TLE |
排名：1/15；总分：160
T1 用了 40 分钟切掉，后三题均为部分分。只写了最基础的一档，头部的人不在，别人又大挂分，于是拿下 rk1。
T1 路径
原图是 DAG，那拓扑排一下然后简单 dp 统计到每个点的路径上能经过的特殊点的最大值是多少。
#include <bits/stdc++.h>
#define il inlineusing namespace std;const int bufsz = 1 << 20;
char ibuf[bufsz], *p1 = ibuf, *p2 = ibuf;
#define getchar() (p1 == p2 && (p2 = (p1 = ibuf) + fread(ibuf, 1, bufsz, stdin), p1 == p2) ? EOF : *p1++)
il int read() {int x = 0; char ch = getchar(); bool t = 0;while (ch < '0' || ch > '9') {t ^= ch == '-'; ch = getchar();}while (ch >= '0' && ch <= '9') {x = (x << 1) + (x << 3) + (ch ^ 48); ch = getchar();}return t ? -x : x;
}
const int N = 1e6 + 10;
int n, m, kk;
int tag[N], rudu[N];
vector<int> G[N];
queue<int> q;
int f[N];
il int solve() {n = read(), m = read();for (int i = 1; i <= n; i++) {G[i].clear();tag[i] = rudu[i] = f[i] = 0;}for (int i = 1; i <= m; i++) {int x = read(), y = read();G[x].push_back(y);rudu[y]++;}kk = read();for (int i = 1; i <= kk; i++) {int x = read();tag[x] = 1;}while (!q.empty()) q.pop();for (int i = 1; i <= n; i++) {if (rudu[i] == 0) q.push(i);}while (!q.empty()) {int x = q.front(); q.pop();f[x] += tag[x];for (int y : G[x]) {f[y] = max(f[y], f[x]);rudu[y]--;if (rudu[y] == 0) q.push(y);}}int ans = 0;for (int i = 1; i <= n; i++) {ans |= (f[i] == kk);}if (ans) {printf("Yes\n");} else {printf("No\n");}return 0;
}
int main() {int qq = read();while (qq--) {solve();}return 0;
}