2020牛客暑期多校训练营(第一场)

Tsukkomi

叉姐出的题,难哭了 我可能是在打危机合约 QAQ


Problem F. Infinite String Comparision

Description

对于一个字符串 xx ,定义 x=xxxx^\infty=xxx\dots .
给定仅由小写字母构成的字符串 a,ba,b (1a,b105)\left(1\leq\left|a\right|,\left|b\right|\leq10^5\right) .
aa^\inftybb^\infty 的字典序关系,输出 =,<,>=,<,> 其中一种。
多组测试,保证 (a+b)2×106\sum\left(\left|a\right|+\left|b\right|\right)\leq2\times10^6 .

Solution

以下内容参考 后缀自动机·张 的文章:Periodicity Lemma

Periodicity Lemma

若字符串 ss 有循环节 p,qp,qp+qs+gcd(p,q)p+q\leq\left|s\right|+\gcd\left(p,q\right) ,则 gcd(p,q)\gcd\left(p,q\right) 也是 ss 的循环节。

Proof

p=qp=q 时显然成立,不妨设 p>qp>q .
易证 pqp-qss 的长度为 sq\left|s\right|-q 的前缀和后缀的循环节。
又因为

p+qs+gcd(p,q)    (pq)+q(sq)+gcd(pq,q)p+q\leq\left|s\right|+\gcd\left(p,q\right)\iff\left(p-q\right)+q\leq\left(\left|s\right|-q\right)+\gcd\left(p-q,q\right)

gcd(p,q)\gcd\left(p,q\right) 也是 ss 的长度为 sq\left|s\right|-q 的前缀和后缀的循环节。
显然 gcd(p,q)(pq)\gcd\left(p,q\right)\mid\left(p-q\right) ,故 gcd(p,q)pq\gcd\left(p,q\right)\leq p-q .
p+qs+pqp+q\leq\left|s\right|+p-q ,亦即 qsqq\leq\left|s\right|-q .
因为 gcd(p,q)q\gcd\left(p,q\right)\mid q ,故 gcd(p,q)\gcd\left(p,q\right) 也是 ss 的长度为 qq 的前缀的循环节。
综上,gcd(p,q)\gcd\left(p,q\right)ss 的循环节。

QED

Solution 1

std 解法。

k=a+bgcd(a,b)k=\left|a\right|+\left|b\right|-\gcd\left(\left|a\right|,\left|b\right|\right) .
Periodicity Lemma 可知,若 aa^\inftybb^\infty 的前 kk 位相同,则 a=ba^\infty=b^\infty .
因此,只需比较 aa^\inftybb^\infty 的前 kk 位即可。

时间复杂度:O((a+b))O(\sum\left(\left|a\right|+\left|b\right|\right)) .

Solution 2

不需要上述 Lemma 的解法。

aa^\inftybb^\infty 视为 2626 进制的 无限循环小数 ,则

a<b    a26a1<b26b1    ab<baa^\infty<b^\infty\iff\frac a{26^{\left|a\right|}-1}<\frac b{26^{\left|b\right|}-1}\iff ab<ba

因此 aa^\inftybb^\infty 的字典序关系与 ababbaba 的字典序关系相同。

时间复杂度:O((a+b))O(\sum\left(\left|a\right|+\left|b\right|\right)) .

Code

Solution 1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
#include <bits/stdc++.h>
using namespace std;

const int N = 1e5 + 5;
char a[N], b[N];

void solve(void);
int gcd(int a, int b);

int main(void) {
while (~scanf("%s%s", a, b)) solve();
return 0;
}

void solve(void) {
int la = strlen(a), lb = strlen(b), lg = gcd(la, lb);
for (int i = 0; i < la + lb - lg; i++) {
int x = i % la, y = i % lb;
if (a[x] ^ b[y]) return puts(a[x] < b[y] ? "<" : ">"), void();
}
puts("=");
}

int gcd(int a, int b) {
for (int t; b;) t = a % b, a = b, b = t;
return a;
}

Solution 2

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#include <bits/stdc++.h>
using namespace std;

string a, b;

void solve(void);

int main(void) {
while (cin >> a >> b) solve();
return 0;
}

void solve(void) {
if (a + b == b + a) return puts("="), void();
puts(a + b < b + a ? "<" : ">");
}

Problem J. Easy Integration

Description

给定 nn (1n106)\left(1\leq n\leq10^6\right) ,求

01(xx2)ndx\int_0^1\left(x-x^2\right)^n\mathrm dx

若答案的最简分数表示是 pq\frac pq ,输出 pqmod998244353\frac pq\bmod998244353 .
多组测试,保证测试组数不超过 10510^5 .

Solution

积分有两种求法。
一种是 分部积分法 ,即

01(xx2)ndx=01xn(1x)ndx=1n+101(1x)ndxn+1=1n+1(xn+1(1x)n01+n01xn+1(1x)n1dx)=nn+101xn+1(1x)n1dx=nn+11n+201(1x)n1dxn+2=nn+11n+2(xn+2(1x)n101+(n1)01xn+2(1x)n2dx)=nn+1n1n+201xn+2(1x)n2dx=(n!)2(2n)!01x2ndx=(n!)2(2n+1)!\begin{aligned} \int_0^1\left(x-x^2\right)^n\mathrm dx&=\int_0^1x^n\left(1-x\right)^n\mathrm dx\\ &=\frac1{n+1}\int_0^1\left(1-x\right)^n\mathrm dx^{n+1}\\ &=\frac1{n+1}\left(x^{n+1}\left(1-x\right)^n\bigg|_0^1+n\int_0^1x^{n+1}\left(1-x\right)^{n-1}\mathrm dx\right)\\ &=\frac n{n+1}\int_0^1x^{n+1}\left(1-x\right)^{n-1}\mathrm dx\\ &=\frac n{n+1}\cdot\frac1{n+2}\int_0^1\left(1-x\right)^{n-1}\mathrm dx^{n+2}\\ &=\frac n{n+1}\cdot\frac1{n+2}\left(x^{n+2}\left(1-x\right)^{n-1}\bigg|_0^1+\left(n-1\right)\int_0^1x^{n+2}\left(1-x\right)^{n-2}\mathrm dx\right)\\ &=\frac n{n+1}\cdot\frac{n-1}{n+2}\int_0^1x^{n+2}\left(1-x\right)^{n-2}\mathrm dx\\ &=\frac{\left(n!\right)^2}{\left(2n\right)!}\int_0^1x^{2n}\mathrm dx\\ &=\frac{\left(n!\right)^2}{\left(2n+1\right)!} \end{aligned}

另一种则是 欧拉积分 ,即

01(xx2)ndx=01xn(1x)ndx=B(n+1,n+1)=Γ(n+1)Γ(n+1)Γ(2n+2)=(n!)2(2n+1)!\begin{aligned} \int_0^1\left(x-x^2\right)^n\mathrm dx&=\int_0^1x^n\left(1-x\right)^n\mathrm dx\\ &=\Beta\left(n+1,n+1\right)\\ &=\frac{\Gamma\left(n+1\right)\Gamma\left(n+1\right)}{\Gamma\left(2n+2\right)}\\ &=\frac{\left(n!\right)^2}{\left(2n+1\right)!} \end{aligned}

预处理 阶乘乘法逆元 即可。

时间复杂度:O(n)\mathcal O\left(n\right) .

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
#include <bits/stdc++.h>
using namespace std;

const int N = 1e6 + 5;
const int p = 998244353;
int n;
int fac[N], fav[N << 1];

void init(void);
int inv(int x);

int main(void) {
init();
while (~scanf("%d", &n))
printf("%d\n", fac[n] * 1ll * fac[n] % p * fav[2 * n + 1] % p);
}

void init(void) {
fac[0] = 1;
for (int i = 1; i < N; i++) fac[i] = fac[i - 1] * 1ll * i % p;
fav[2 * N - 1] = fac[N - 1];
for (int i = N; i < 2 * N; i++)
fav[2 * N - 1] = fav[2 * N - 1] * 1ll * i % p;
fav[2 * N - 1] = inv(fav[2 * N - 1]);
for (int i = 2 * N - 2; i; i--) fav[i] = fav[i + 1] * 1ll * (i + 1) % p;
}

int inv(int x) { return x == 1 ? 1 : (p - p / x) * 1ll * inv(p % x) % p; }

Problem H. Minimum-cost Flow

Description

给定一个 nn (2n50)\left(2\leq n\leq50\right) 个点 mm (1m102)\left(1\leq m\leq10^2\right) 条前向弧的容量网络。
ii 条前向弧以 (ai,bi,ci)\left(a_i,b_i,c_i\right) (1ci105)\left(1\leq c_i\leq10^5\right) 的形式给出,表示弧 (ai,bi)\left(a_i,b_i\right) 的费用为 cic_i .
现有 qq (1q105)\left(1\leq q\leq10^5\right) 次询问,第 ii 次询问以 (ui,vi)\left(u_i,v_i\right) (0ui,vi109, vi>0)\left(0\leq u_i,v_i\leq10^9,\ v_i>0\right) 的形式给出。
询问 (ui,vi)\left(u_i,v_i\right) 表示求当前向弧容量均为 uivi\frac{u_i}{v_i} 时,单位流量从点 11 流至点 nn 的最小费用。
若答案的最简分数表示是 pq\frac pq 则以 p/q​ 的形式输出,若答案不存在则输出字符串 NaN .
多组测试,保证 m104, q106\sum m\leq10^4,\ \sum q\leq10^6 .

Solution

令前向弧容量均为 11 ,跑 费用流 求出所有的 增广路 并按费用 从小到大 排序。
这里尽量用 多路增广 ,合并费用相同的增广路即可。
询问 (u,v)\left(u,v\right) 相当于将每条增广路的流量增加至 uu 倍,求总流量为 vv 时的最小费用。
可用 前缀和 ++ 二分 进行优化,单次询问可在 O(logm)\mathcal O\left(\log m\right) 的时间内完成。

时间复杂度:O((Maximum Flow+qlogm))\mathcal O\left(\sum\left(\mathrm{Maximum\ Flow}+q\log m\right)\right) .

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

const int N = 55;
const int M = 1e2 + 5;
const int inf = 1e9 + 5;
int n, m, q;
int edg = 1, head[N], to[M << 1], nxt[M << 1], cap[M << 1], wei[M << 1];
int s, t, ct, dis[N], cur[N], pfl[M];
ll c, g, co[M], pco[M];
bool vis[N];
queue<int> qu;

void solve(void);
void add_edge(int u, int v, int c, int w);
void mcmf(void);
bool spfa(void);
int dfs(int u, int c = inf);
ll gcd(ll a, ll b);

int main(void) {
while (~scanf("%d%d", &n, &m)) solve();
return 0;
}

void solve(void) {
edg = 1, memset(head, 0, (n + 1) * sizeof(int));
for (int i = 1, a, b, c; i <= m; i++)
scanf("%d%d%d", &a, &b, &c), add_edge(a, b, 1, c);
s = 1, t = n, ct = 0, mcmf(), scanf("%d", &q);
for (int i = 1; i <= ct; i++) pfl[i] += pfl[i - 1], pco[i] += pco[i - 1];
for (int i = 1, u, v, k; i <= q; i++) {
scanf("%d%d", &u, &v), k = 0;
if (u) k = lower_bound(pfl + 1, pfl + ct + 1, ceil(v * 1.0 / u)) - pfl;
if (!u || k > ct) {
puts("NaN");
continue;
}
c = u * pco[k - 1] + (v - u * 1ll * pfl[k - 1]) * co[k], g = gcd(c, v);
printf("%lld/%lld\n", c / g, v / g);
}
}

inline void add_edge(int u, int v, int c, int w) {
to[++edg] = v, cap[edg] = c, wei[edg] = w;
nxt[edg] = head[u], head[u] = edg;
to[++edg] = u, cap[edg] = 0, wei[edg] = -w;
nxt[edg] = head[v], head[v] = edg;
}

void mcmf(void) {
for (int d; spfa();) {
memcpy(cur, head, (n + 1) * sizeof(int));
ct++, pfl[ct] = d = dfs(s), co[ct] = dis[t], pco[ct] = d * dis[t];
}
}

bool spfa(void) {
memset(dis, 63, sizeof(head)), dis[s] = 0, qu.push(s);
for (int u; !qu.empty();) {
vis[u = qu.front()] = false, qu.pop();
for (int i = head[u]; i; i = nxt[i]) {
int v = to[i];
if (!cap[i] || dis[v] <= dis[u] + wei[i]) continue;
dis[v] = dis[u] + wei[i];
if (!vis[v]) vis[v] = true, qu.push(v);
}
}
return dis[t] < inf;
}

int dfs(int u, int c) {
if (u == t) return c;
vis[u] = true;
int f = 0;
for (int &i = cur[u]; i && f < c; i = nxt[i]) {
int v = to[i];
if (vis[v] || !cap[i] || dis[v] < dis[u] + wei[i]) continue;
int d = dfs(v, min(c - f, cap[i]));
f += d, cap[i] -= d, cap[i ^ 1] += d;
}
vis[u] = false;
return (dis[u] = f ? dis[u] : -inf), f;
}

ll gcd(ll a, ll b) {
for (ll t; b;) t = a % b, a = b, b = t;
return a;
}

Problem A. B-Suffix Array

Description

定义函数 BB ,对于长度为 kk 的字符串 tt ,有 B(t)=bB\left(t\right)=b .
其中 bb 是一个长度为 kk 的序列,满足

bi={min1j<i, tj=ti(ij)j[1,i), tj=ti0otherwiseb_i=\begin{cases} \min\limits_{1\leq j<i,\ t_j=t_i}\left(i-j\right)&\exists j\in\left[1,i\right),\ t_j=t_i\\ 0&\mathrm{otherwise} \end{cases}

给定仅由字符 a, b 构成的长度为 nn (1n105)\left(1\leq n\leq10^5\right) 的字符串 ss .
i[1,n]\forall i\in\left[1,n\right] ,记 Si=sisi+1snS_i=s_is_{i+1}\dots s_n .
求一个 1n1\sim n 的排列 pp ,使得在字典序意义下对 i(1,n]\forall i\in\left(1,n\right]B(Spi1)<B(Spi)B\left(S_{p_{i-1}}\right)<B\left(S_{p_i}\right) .
多组测试,保证 n106\sum n\leq10^6 .

Solution

定义函数 CC ,对于长度为 kk 的字符串 tt ,有 C(t)=cC\left(t\right)=c .
其中 cc 是一个长度为 k+1k+1 的序列,满足

ci={k+1i=k+1mini<jk, tj=ti(ji)j(i,k], tj=tikotherwisec_i=\begin{cases} k+1&i=k+1\\ \min\limits_{i<j\leq k,\ t_j=t_i}\left(j-i\right)&\exists j\in\left(i,k\right],\ t_j=t_i\\ k&\mathrm{otherwise} \end{cases}

Lemma

对于仅由两个字符构成的字符串 s,ts,t ,在字典序意义下有

B(s)<B(t)    C(s)>C(t)B\left(s\right)<B\left(t\right)\iff C\left(s\right)>C\left(t\right)

感性理解一下,具体证明见:Parameterized Suffix Arrays for Binary Strings

Solution 1

std 解法。

B(s)=b, C(s)=cB\left(s\right)=b,\ C\left(s\right)=c .
Ci=cici+1cn+1C_i=c_ic_{i+1}\dots c_{n+1} ,则 C(Si)=CiC\left(S_i\right)=C_i .
根据上述 Lemma ,在字典序意义下对 i(1,n]\forall i\in\left(1,n\right]

B(Spi1)<B(Spi)    C(Spi1)>C(Spi)    Cpi1>CpiB\left(S_{p_{i-1}}\right)<B\left(S_{p_i}\right)\iff C\left(S_{p_{i-1}}\right)>C\left(S_{p_i}\right)\iff C_{p_{i-1}}>C_{p_i}

后缀数组 求序列 cc 的排名 从大到小 的后缀即可。

时间复杂度:O((nlogn))\mathcal O\left(\sum\left(n\log n\right)\right) .

Solution 2

不需要上述 Lemma 的解法。
以下序列间大小关系均在字典序意义下。

对于仅由两个字符构成的字符串 tt ,令 B(t)=pqB\left(t\right)=pq .
tt 含两种字符时,pp 形如序列 01110011\dots10 .
tt 仅含一种字符时,pp 形如序列 0111011\dots1 .

B(s)=bB\left(s\right)=b ,沿用上述定义记 B(Si)=PiQiB\left(S_i\right)=P_iQ_i .
fif_iSiS_i 所含字符种数,gi=Pi+[fi=1]g_i=\left|P_i\right|+\left[f_i=1\right] .
Px=0, Py=00P_x=0,\ P_y=00 ,则 B(Sx)<B(Sy), (gx,Qx)=(gy,Qy)B\left(S_x\right)<B\left(S_y\right),\ \left(g_x,Q_x\right)=\left(g_y,Q_y\right) .
除此之外,易证

B(Sx)<B(Sy)    (gx,Qx)<(gy,Qy)B\left(S_x\right)<B\left(S_y\right)\iff\left(g_x,Q_x\right)<\left(g_y,Q_y\right)

显然 gig_i线性 预处理,QiQ_ibb 的后缀,对应排名可用 后缀数组 求。

时间复杂度:O((nlogn))\mathcal O\left(\sum\left(n\log n\right)\right) .

Code

Solution 1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
#include <bits/stdc++.h>
using namespace std;

const int N = 1e5 + 5;
int n;
char s[N];
int nxt[2], c[N];
int sa[N], rk[N], tp[N << 1], cnt[N];

void solve(void);
void get_sa(int n, int m, int *a);
void cnt_sort(int n, int m);
bool cmp(int a, int b, int w);

int main(void) {
while (~scanf("%d%s", &n, s + 1)) solve();
return 0;
}

void solve(void) {
nxt[0] = nxt[1] = 0;
for (int i = n, x; i; i--)
x = s[i] - 'a', c[i] = nxt[x] ? nxt[x] - i : n, nxt[x] = i;
c[n + 1] = n + 1, get_sa(n + 1, n + 1, c);
for (int i = n; i; i--) printf("%d%c", sa[i], " \n"[i == 1]);
}

void get_sa(int n, int m, int *a) {
for (int i = 1; i <= n; i++) rk[i] = a[i], tp[i] = i, tp[i + n] = 0;
cnt_sort(n, m);
for (int w = 1, p = 0, x; p < n && w < n; w <<= 1, m = p) {
for (p = 0, x = 1; x <= w; x++) tp[++p] = n - w + x;
for (int i = 1; i <= n; i++)
if (sa[i] > w) tp[++p] = sa[i] - w;
cnt_sort(n, m), memcpy(tp, rk, (n + 1) * sizeof(int));
rk[sa[1]] = p = 1;
for (int i = 2; i <= n; i++)
rk[sa[i]] = cmp(sa[i - 1], sa[i], w) ? ++p : p;
}
}

void cnt_sort(int n, int m) {
memset(cnt, 0, (m + 1) * sizeof(int));
for (int i = 1; i <= n; i++) cnt[rk[i]]++;
for (int i = 1; i <= m; i++) cnt[i] += cnt[i - 1];
for (int i = n; i; i--) sa[cnt[rk[tp[i]]]--] = tp[i];
}

inline bool cmp(int a, int b, int w) {
return tp[a] == tp[b] ? tp[a + w] < tp[b + w] : tp[a] < tp[b];
}

Solution 2

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
#include <bits/stdc++.h>
using namespace std;

struct suf {
int l, r;
suf(int a = 0, int b = 0): l(a), r(b) {}
bool operator<(const suf &t) const;
};

const int N = 1e5 + 5;
int n;
char s[N];
int lst[2], nxt[2], b[N];
int sa[N], rk[N], tp[N << 1], cnt[N];
suf ans[N];

void solve(void);
void get_sa(int n, int m, int *a);
void cnt_sort(int n, int m);
bool cmp(int a, int b, int w);

int main(void) {
while (~scanf("%d%s", &n, s + 1)) solve();
return 0;
}

void solve(void) {
lst[0] = lst[1] = 0, nxt[0] = nxt[1] = n + 1;
for (int i = 1, x; i <= n; i++)
x = s[i] - 'a', b[i] = lst[x] ? i - lst[x] + 1 : 1, lst[x] = i;
get_sa(n, n, b), rk[n + 1] = 0, rk[n + 2] = -1;
for (int i = n, x; i; i--)
x = s[i] - 'a', ans[i] = suf(i, nxt[!x]), nxt[x] = i;
sort(ans + 1, ans + n + 1);
for (int i = 1; i <= n; i++) printf("%d%c", ans[i].l, " \n"[i == n]);
}

void get_sa(int n, int m, int *a) {
for (int i = 1; i <= n; i++) rk[i] = a[i], tp[i] = i, tp[i + n] = 0;
cnt_sort(n, m);
for (int w = 1, p = 0, x; p < n && w < n; w <<= 1, m = p) {
for (p = 0, x = 1; x <= w; x++) tp[++p] = n - w + x;
for (int i = 1; i <= n; i++)
if (sa[i] > w) tp[++p] = sa[i] - w;
cnt_sort(n, m), memcpy(tp, rk, (n + 1) * sizeof(int));
rk[sa[1]] = p = 1;
for (int i = 2; i <= n; i++)
rk[sa[i]] = cmp(sa[i - 1], sa[i], w) ? ++p : p;
}
}

void cnt_sort(int n, int m) {
memset(cnt, 0, (m + 1) * sizeof(int));
for (int i = 1; i <= n; i++) cnt[rk[i]]++;
for (int i = 1; i <= m; i++) cnt[i] += cnt[i - 1];
for (int i = n; i; i--) sa[cnt[rk[tp[i]]]--] = tp[i];
}

inline bool cmp(int a, int b, int w) {
return tp[a] == tp[b] ? tp[a + w] < tp[b + w] : tp[a] < tp[b];
}

bool suf::operator<(const suf &t) const {
return r - l == t.r - t.l ? rk[r + 1] < rk[t.r + 1] : r - l < t.r - t.l;
}

Problem I. 1 or 2

Description

给定一个 nn (1n50)\left(1\leq n\leq50\right) 个点 mm (1m102)\left(1\leq m\leq10^2\right) 条边的无向图。
ii 条边以 (ai,bi)\left(a_i,b_i\right) 的形式给出,无重边和自环。
给定一个长度为 nn 的序列 dd (1di2)\left(1\leq d_i\leq2\right) .
求是否存在一个子图使得点 ii 的度恰为 did_i ,输出字符串 Yes / No .
多组测试,保证测试组数不超过 10210^2 .

Solution

考虑如下建新图:

  • 对于每个点 uu ,将 uu 拆为 dud_u 个点,第 ii 个点记为 uiu_i .
  • 对于每条边 (u,v)\left(u,v\right) ,新增两个辅助点 x,yx,y .
    uiu_i 均和 xx 连边,viv_i 均和 yy 连边,xxyy 连边。

则原图有符合要求的子图 当且仅当 新图有 完美匹配 ,用 带花树 求解即可。

时间复杂度:O(8(n+m)3)\mathcal O\left(8\left(n+m\right)^3\right) .

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
#include <bits/stdc++.h>
using namespace std;

const int N = 55;
const int M = 1e2 + 5;
int n, m, d[N];
int idx, tim, far[(N + M) << 1], ti[(N + M) << 1], id[N][2];
int edg, head[(N + M) << 1], to[M << 4], nxt[M << 4];
int mate[(N + M) << 1], link[(N + M) << 1], vis[(N + M) << 1];
queue<int> q;

void solve(void);
void add_edge(int u, int v);
int edmonds(void);
bool bfs(int x);
int find(int x);
int lca(int u, int v);
void flower(int u, int v, int f);

int main(void) {
while (~scanf("%d%d", &n, &m)) solve();
return 0;
}

void solve(void) {
idx = 0;
for (int i = 1; i <= n; i++) {
scanf("%d", d + i);
for (int j = 0; j < d[i]; j++) id[i][j] = ++idx;
}
edg = 1, memset(head, 0, (idx + 2 * m + 1) * sizeof(int));
for (int i = 1, a, b, x, y; i <= m; i++) {
scanf("%d%d", &a, &b), x = ++idx, y = ++idx, add_edge(x, y);
for (int j = 0; j < d[a]; j++) add_edge(id[a][j], x);
for (int j = 0; j < d[b]; j++) add_edge(id[b][j], y);
}
puts(2 * edmonds() == idx ? "Yes" : "No");
}

inline void add_edge(int u, int v) {
to[++edg] = v, nxt[edg] = head[u], head[u] = edg;
to[++edg] = u, nxt[edg] = head[v], head[v] = edg;
}

int edmonds(void) {
int ans = 0;
for (int i = 1; i <= idx; i++) mate[i] = link[i] = 0;
for (int i = 1; i <= idx; i++) ans += !mate[i] && bfs(i);
return ans;
}

bool bfs(int x) {
for (int i = 1; i <= idx; i++) far[i] = i, vis[i] = ti[i] = 0;
while (!q.empty()) q.pop();
tim = 0, vis[x] = 1, q.push(x);
for (int u; !q.empty();) {
u = q.front(), q.pop();
for (int i = head[u]; i; i = nxt[i]) {
int v = to[i];
if (vis[v] == 2) continue;
if (vis[v]) {
if (find(u) ^ find(v)) {
int f = lca(u, v);
flower(u, v, f), flower(v, u, f);
}
continue;
}
vis[v] = 2, link[v] = u;
if (!mate[v]) {
for (int t = 1; t; v = t)
t = mate[link[v]], mate[v] = link[v], mate[link[v]] = v;
return true;
}
vis[mate[v]] = 1, q.push(mate[v]);
}
}
return false;
}

int find(int x) { return x == far[x] ? x : far[x] = find(far[x]); }

int lca(int u, int v) {
for (tim++; ti[u] < tim; swap(u, v))
if (u) ti[u] = tim, u = find(link[mate[u]]);
return u;
}

void flower(int u, int v, int f) {
for (; find(u) ^ f; u = link[v]) {
link[u] = v, v = mate[u], far[u] = far[v] = f;
if (vis[v] == 2) vis[v] = 1, q.push(v);
}
}

Welcome to my other publishing channels