# 【CodeForces】CodeForces Round #477 (Div. 1 + Div. 2) 题解

xiaoxiao2021-02-28  19

【比赛链接】

Div. 1Div. 2

【题解链接】

【Div.2 A】Mind the Gap

【思路要点】

【代码】

#include<bits/stdc++.h> using namespace std; const int MAXN = 100005; template <typename T> void chkmax(T &x, T y) {x = max(x, y); } template <typename T> void chkmin(T &x, T y) {x = min(x, y); } template <typename T> void read(T &x) { x = 0; int f = 1; char c = getchar(); for (; !isdigit(c); c = getchar()) if (c == '-') f = -f; for (; isdigit(c); c = getchar()) x = x * 10 + c - '0'; x *= f; } template <typename T> void write(T x) { if (x < 0) x = -x, putchar('-'); if (x > 9) write(x / 10); putchar(x % 10 + '0'); } template <typename T> void writeln(T x) { write(x); puts(""); } int n, s, a[MAXN]; bool valid(int x) { if (x + s < a[1]) return true; if (x - s > a[n]) return true; for (int i = 1; i < n; i++) if (x - s > a[i] && x + s < a[i + 1]) return true; return false; } int main() { read(n), read(s); for (int i = 1; i <= n; i++) { int x, y; read(x), read(y); a[i] = x * 60 + y; } int ans = 0; while (!valid(ans)) ans++; printf("%d %d\n", ans / 60, ans % 60); return 0; }

【Div.2 B】Watering System

【思路要点】

【代码】

#include<bits/stdc++.h> using namespace std; const int MAXN = 100005; template <typename T> void chkmax(T &x, T y) {x = max(x, y); } template <typename T> void chkmin(T &x, T y) {x = min(x, y); } template <typename T> void read(T &x) { x = 0; int f = 1; char c = getchar(); for (; !isdigit(c); c = getchar()) if (c == '-') f = -f; for (; isdigit(c); c = getchar()) x = x * 10 + c - '0'; x *= f; } template <typename T> void write(T x) { if (x < 0) x = -x, putchar('-'); if (x > 9) write(x / 10); putchar(x % 10 + '0'); } template <typename T> void writeln(T x) { write(x); puts(""); } int main() { int n, A, B, C, T, ans = 0; read(n), read(A), read(B), read(C), read(T); for (int i = 1; i <= n; i++) { int x; read(x); ans += A; if (C >= B) ans += (T - x) * (C - B); } writeln(ans); return 0; }

【Div.2 C/Div.1 A】Stairs and Elevators

【思路要点】

【代码】

#include<bits/stdc++.h> using namespace std; const int MAXN = 100005; template <typename T> void chkmax(T &x, T y) {x = max(x, y); } template <typename T> void chkmin(T &x, T y) {x = min(x, y); } template <typename T> void read(T &x) { x = 0; int f = 1; char c = getchar(); for (; !isdigit(c); c = getchar()) if (c == '-') f = -f; for (; isdigit(c); c = getchar()) x = x * 10 + c - '0'; x *= f; } template <typename T> void write(T x) { if (x < 0) x = -x, putchar('-'); if (x > 9) write(x / 10); putchar(x % 10 + '0'); } template <typename T> void writeln(T x) { write(x); puts(""); } int func(int dist, int v) { return dist / v + (dist % v != 0); } int a[MAXN], b[MAXN]; int main() { int r, n, m, v; read(r), read(r), read(n), read(m), read(v); for (int i = 1; i <= n; i++) read(a[i]); for (int i = 1; i <= m; i++) read(b[i]); int q; read(q); for (int i = 1; i <= q; i++) { int sx, sy, tx, ty; read(sx), read(sy); read(tx), read(ty); if (sx == tx) { writeln(abs(sy - ty)); continue; } int tmp = lower_bound(a + 1, a + n + 1, sy) - a; int tnp = tmp - 1; int ans = 2e9; if (tmp <= n) chkmin(ans, abs(a[tmp] - sy) + abs(a[tmp] - ty) + abs(sx - tx)); if (tnp >= 1) chkmin(ans, abs(a[tnp] - sy) + abs(a[tnp] - ty) + abs(sx - tx)); tmp = lower_bound(b + 1, b + m + 1, sy) - b; tnp = tmp - 1; if (tmp <= m) chkmin(ans, abs(b[tmp] - sy) + abs(b[tmp] - ty) + func(abs(sx - tx), v)); if (tnp >= 1) chkmin(ans, abs(b[tnp] - sy) + abs(b[tnp] - ty) + func(abs(sx - tx), v)); writeln(ans); } return 0; }

【Div.2 D/Div.1 B】Resource Distribution

【思路要点】

【代码】

#include<bits/stdc++.h> using namespace std; const int MAXN = 300005; template <typename T> void chkmax(T &x, T y) {x = max(x, y); } template <typename T> void chkmin(T &x, T y) {x = min(x, y); } template <typename T> void read(T &x) { x = 0; int f = 1; char c = getchar(); for (; !isdigit(c); c = getchar()) if (c == '-') f = -f; for (; isdigit(c); c = getchar()) x = x * 10 + c - '0'; x *= f; } template <typename T> void write(T x) { if (x < 0) x = -x, putchar('-'); if (x > 9) write(x / 10); putchar(x % 10 + '0'); } template <typename T> void writeln(T x) { write(x); puts(""); } struct info {int val, home; }; info a[MAXN]; bool cmp(info a, info b) {return a.val < b.val; } int main() { int n, x, y; read(n), read(x), read(y); for (int i = 1; i <= n; i++) read(a[i].val), a[i].home = i; sort(a + 1, a + n + 1, cmp); int posx = 0, posy = 0; for (int i = n; i >= 1; i--) { int cnt = x / a[i].val + (x % a[i].val != 0); if (i + cnt - 1 <= n) { posx = i; break; } } if (posx == 0) { printf("No\n"); return 0; } for (int i = n; i >= 1; i--) { int cnt = y / a[i].val + (y % a[i].val != 0); if (i + cnt - 1 <= n) { posy = i; break; } } if (posy == 0) { printf("No\n"); return 0; } for (int i = 1; i <= n; i++) { int cntx = x / a[i].val + (x % a[i].val != 0); if (i + cntx <= posy) { printf("Yes\n%d %d\n", cntx, n - posy + 1); for (int j = 1; j <= cntx; j++) printf("%d ", a[i + j - 1].home); printf("\n"); for (int j = posy; j <= n; j++) printf("%d ", a[j].home); printf("\n"); return 0; } int cnty = y / a[i].val + (y % a[i].val != 0); if (i + cnty <= posx) { printf("Yes\n%d %d\n", n - posx + 1, cnty); for (int j = posx; j <= n; j++) printf("%d ", a[j].home); printf("\n"); for (int j = 1; j <= cnty; j++) printf("%d ", a[i + j - 1].home); printf("\n"); return 0; } } printf("No\n"); return 0; }

【Div.2 E/Div.1 C】Big Secret

【思路要点】

【代码】

#include<bits/stdc++.h> using namespace std; const int MAXN = 100005; const int MAXLOG = 61; const int MAXP = 1e7 + 5; const long long INF = 9e18; template <typename T> void chkmax(T &x, T y) {x = max(x, y); } template <typename T> void chkmin(T &x, T y) {x = min(x, y); } template <typename T> void read(T &x) { x = 0; int f = 1; char c = getchar(); for (; !isdigit(c); c = getchar()) if (c == '-') f = -f; for (; isdigit(c); c = getchar()) x = x * 10 + c - '0'; x *= f; } template <typename T> void write(T x) { if (x < 0) x = -x, putchar('-'); if (x > 9) write(x / 10); putchar(x % 10 + '0'); } template <typename T> void writeln(T x) { write(x); puts(""); } struct SegmentTree { struct Node { int lc, rc; int sum; } a[MAXP]; int root, size; void insert(int &root, int depth, long long x, int d) { if (root == 0) root = ++size; a[root].sum += d; if (depth == -1) return; long long tmp = 1ll << depth; if (tmp & x) insert(a[root].rc, depth - 1, x, d); else insert(a[root].lc, depth - 1, x, d); } void insert(long long x, int d) { insert(root, MAXLOG, x, d); } long long query(int root, int depth, long long x, bool type) { if (depth == -1) return 0; long long tmp = 1ll << depth; if (type) { if (x & tmp) { if (a[a[root].rc].sum) return query(a[root].rc, depth - 1, x, type) + tmp; else return query(a[root].lc, depth - 1, x, type); } else { if (a[a[root].lc].sum) return query(a[root].lc, depth - 1, x, type); else return query(a[root].rc, depth - 1, x, type) + tmp; } } else { if (x & tmp) { if (a[a[root].lc].sum) return query(a[root].lc, depth - 1, x, type); else return -INF; } else { if (a[a[root].lc].sum) { long long tnp = query(a[root].lc, depth - 1, x, type); if (tnp > 0) return tnp; } if (a[a[root].rc].sum) return query(a[root].rc, depth - 1, x, true) + tmp; else return -INF; } } } long long query(long long x) { long long ans = query(root, MAXLOG, x, false); if (ans > 0) insert(ans, -1); return ans; } } ST; long long ans[MAXN]; int main() { int n; read(n); long long now = 0; for (int i = 1; i <= n; i++) { long long x; read(x); ST.insert(x, 1); } for (int i = 1; i <= n; i++) { long long tmp = ST.query(now); if (tmp <= 0) { printf("No\n"); return 0; } now ^= tmp; ans[i] = tmp; } printf("Yes\n"); for (int i = 1; i <= n; i++) write(ans[i]), putchar(' '); return 0; }

【Div.2 F/Div.1 D】Aztec Catacombs

【思路要点】

【代码】

#include<bits/stdc++.h> using namespace std; const int MAXN = 300005; template <typename T> void chkmax(T &x, T y) {x = max(x, y); } template <typename T> void chkmin(T &x, T y) {x = min(x, y); } template <typename T> void read(T &x) { x = 0; int f = 1; char c = getchar(); for (; !isdigit(c); c = getchar()) if (c == '-') f = -f; for (; isdigit(c); c = getchar()) x = x * 10 + c - '0'; x *= f; } template <typename T> void write(T x) { if (x < 0) x = -x, putchar('-'); if (x > 9) write(x / 10); putchar(x % 10 + '0'); } template <typename T> void writeln(T x) { write(x); puts(""); } vector <int> a[MAXN], pos; set <int> b[MAXN]; int n, m, degree[MAXN]; bool vis[MAXN]; void bfs() { static int fa[MAXN], q[MAXN], depth[MAXN]; static bool vis[MAXN]; int l, r; q[l = r = 1] = 1, depth[1] = 1, vis[1] = true; while (l <= r) { int tmp = q[l++]; for (unsigned i = 0; i < a[tmp].size(); i++) if (!vis[a[tmp][i]]) { q[++r] = a[tmp][i]; fa[a[tmp][i]] = tmp; vis[a[tmp][i]] = true; depth[a[tmp][i]] = depth[tmp] + 1; } } if (depth[n] != 0 && depth[n] <= 5) { int pos = n; vector <int> ans; ans.push_back(n); while (pos != 1) { pos = fa[pos]; ans.push_back(pos); } writeln(ans.size() - 1); for (unsigned i = ans.size(); i >= 1; i--) printf("%d ", ans[i - 1]); exit(0); } for (int i = 1; i <= r; i++) { int pos = q[i]; if (depth[pos] == 3 && b[pos].count(1) == 0) { writeln(4); printf("%d %d %d %d %d\n", 1, fa[pos], pos, 1, n); exit(0); } } } void work(int x) { vis[x] = true; pos.push_back(x); for (unsigned i = 0; i < a[x].size(); i++) { degree[a[x][i]]++; if (!vis[a[x][i]]) work(a[x][i]); } } int main() { read(n), read(m); for (int i = 1; i <= m; i++) { int x, y; read(x), read(y); a[x].push_back(y); a[y].push_back(x); b[x].insert(y); b[y].insert(x); } bfs(); vis[1] = true; for (unsigned i = 0; i < a[1].size(); i++) { if (vis[a[1][i]]) continue; pos.clear(); work(a[1][i]); int x = 0; for (unsigned j = 0; j < pos.size(); j++) if (degree[pos[j]] < pos.size() - 1) x = pos[j]; if (x == 0) continue; for (unsigned j = 0; j < a[x].size(); j++) { if (a[x][j] == 1) continue; int y = a[x][j]; for (unsigned k = 0; k < a[y].size(); k++) { int z = a[y][k]; if (z != x && z != 1 && b[x].count(z) == 0) { writeln(5); printf("%d %d %d %d %d %d\n", 1, x, y, z, x, n); exit(0); } } } } writeln(-1); return 0; }

【Div.1 E】May Holidays

【思路要点】

【代码】

#include<bits/stdc++.h> using namespace std; const int MAXN = 100005; const int MAXLOG = 20; template <typename T> void chkmax(T &x, T y) {x = max(x, y); } template <typename T> void chkmin(T &x, T y) {x = min(x, y); } template <typename T> void read(T &x) { x = 0; int f = 1; char c = getchar(); for (; !isdigit(c); c = getchar()) if (c == '-') f = -f; for (; isdigit(c); c = getchar()) x = x * 10 + c - '0'; x *= f; } template <typename T> void write(T x) { if (x < 0) x = -x, putchar('-'); if (x > 9) write(x / 10); putchar(x % 10 + '0'); } template <typename T> void writeln(T x) { write(x); puts(""); } vector <int> a[MAXN], b[MAXN], c[MAXN]; int n, m, father[MAXN], val[MAXN], q[MAXN]; int timer, dfn[MAXN], depth[MAXN], parent[MAXN][MAXLOG]; int btot, bsize, bl[MAXN], br[MAXN], belong[MAXN]; int ans, size[MAXN], newfa[MAXN], point[MAXN]; bool flg[MAXN]; int lca(int x, int y) { if (depth[x] < depth[y]) swap(x, y); for (int i = MAXLOG - 1; i >= 0; i--) if (depth[parent[x][i]] >= depth[y]) x = parent[x][i]; if (x == y) return x; for (int i = MAXLOG - 1; i >= 0; i--) if (parent[x][i] != parent[y][i]) { x = parent[x][i]; y = parent[y][i]; } return father[x]; } void dfs(int pos, int fa) { dfn[pos] = ++timer; parent[pos][0] = fa; for (int i = 1; i < MAXLOG; i++) parent[pos][i] = parent[parent[pos][i - 1]][i - 1]; depth[pos] = depth[fa] + 1; for (unsigned i = 0; i < a[pos].size(); i++) dfs(a[pos][i], pos); } void calc(int pos) { for (unsigned i = 0; i < a[pos].size(); i++) { calc(a[pos][i]); size[pos] += size[a[pos][i]]; } val[pos] += size[pos]; if (!flg[pos] && val[pos] <= 0) ans++; } bool cmp(int x, int y) { return dfn[x] < dfn[y]; } int main() { read(n), read(m); for (int i = 2; i <= n; i++) { read(father[i]); a[father[i]].push_back(i); } for (int i = 1; i <= n; i++) read(val[i]), val[i]++; for (int i = 1; i <= m; i++) read(q[i]); dfs(1, 0); bsize = pow(m, 0.618); btot = 0; for (int i = 1; i <= m; i++) { if (i % bsize == 1 % bsize) bl[++btot] = i; belong[i] = btot, br[btot] = i; } for (int t = 1; t <= btot; t++) { static int tmp[MAXN]; int tot = 0; for (int i = bl[t]; i <= br[t]; i++) tmp[++tot] = abs(q[i]); sort(tmp + 1, tmp + tot + 1, cmp); static int stk[MAXN], used[MAXN]; int top = 0, cnt = 0; stk[++top] = used[++cnt] = 1; for (int i = 1; i <= tot; i++) { if (tmp[i] == stk[top]) continue; int Lca = lca(tmp[i], stk[top]); if (Lca == stk[top]) stk[++top] = used[++cnt] = tmp[i]; else { while (dfn[Lca] < dfn[stk[top - 1]]) { newfa[stk[top]] = stk[top - 1]; top--; } newfa[stk[top]] = Lca; top--; if (Lca == stk[top]) stk[++top] = used[++cnt] = tmp[i]; else { stk[++top] = used[++cnt] = Lca; stk[++top] = used[++cnt] = tmp[i]; } } } while (top >= 2) { newfa[stk[top]] = stk[top - 1]; top--; } for (int i = 1; i <= cnt; i++) { int now = used[i], pos = father[now]; b[now].clear(), c[now].clear(); while (pos != newfa[now]) { if (!flg[pos]) b[now].push_back(val[pos]); pos = father[pos]; } sort(b[now].begin(), b[now].end()); int top = -1; for (unsigned i = 0; i < b[now].size(); i++) if (i == 0 || b[now][i] != b[now][i - 1]) b[now][++top] = b[now][i], c[now].push_back(1); else c[now][top]++; b[now].resize(top + 1); point[now] = 0; for (unsigned i = 0; i < b[now].size(); i++) if (b[now][i] <= 0) point[now]++; else break; } memset(size, 0, sizeof(size)); for (int i = bl[t]; i <= br[t]; i++) { int now = abs(q[i]); if (q[i] >= 0) { if (val[now] + size[now] <= 0) ans--; flg[now] = true; int pos = now; while (pos) { size[pos]--; if (!flg[pos] && val[pos] + size[pos] == 0) ans++; if (point[pos] < b[pos].size() && b[pos][point[pos]] + size[pos] <= 0) ans += c[pos][point[pos]++]; pos = newfa[pos]; } } else { if (val[now] + size[now] + 1 <= 0) ans++; flg[now] = false; int pos = now; while (pos) { if (now != pos && !flg[pos] && val[pos] + size[pos] == 0) ans--; size[pos]++; if (point[pos] > 0 && b[pos][point[pos] - 1] + size[pos] > 0) ans -= c[pos][--point[pos]]; pos = newfa[pos]; } } printf("%d ", ans); } ans = 0; memset(size, 0, sizeof(size)); for (int i = bl[t]; i <= br[t]; i++) if (q[i] >= 0) size[q[i]]--, flg[q[i]] = true; else size[-q[i]]++, flg[-q[i]] = false; calc(1); } return 0; }

【Div.1 F】Parametric Circulation

【思路要点】

【代码】

#include<bits/stdc++.h> using namespace std; const int MAXN = 2005; const long long bnd = 1e8; const long long INF = 1e18; template <typename T> void chkmax(T &x, T y) {x = max(x, y); } template <typename T> void chkmin(T &x, T y) {x = min(x, y); } template <typename T> void read(T &x) { x = 0; int f = 1; char c = getchar(); for (; !isdigit(c); c = getchar()) if (c == '-') f = -f; for (; isdigit(c); c = getchar()) x = x * 10 + c - '0'; x *= f; } template <typename T> void write(T x) { if (x < 0) x = -x, putchar('-'); if (x > 9) write(x / 10); putchar(x % 10 + '0'); } template <typename T> void writeln(T x) { write(x); puts(""); } struct edge {int dest; long long flow; unsigned home; }; vector <edge> a[MAXN]; int s, t, n, m, x[MAXN], y[MAXN], dist[MAXN]; long long lk[MAXN], lb[MAXN], rk[MAXN], rb[MAXN]; unsigned curr[MAXN]; long long dinic(int pos, long long limit) { if (pos == t) return limit; long long used = 0; for (unsigned &i = curr[pos]; i < a[pos].size(); i++) if (a[pos][i].flow != 0 && dist[pos] + 1 == dist[a[pos][i].dest]) { long long tmp = dinic(a[pos][i].dest, min(limit - used, a[pos][i].flow)); used += tmp; a[pos][i].flow -= tmp; a[a[pos][i].dest][a[pos][i].home].flow += tmp; if (limit == used) return used; } return used; } bool bfs() { static int q[MAXN], l, r; for (int i = 0; i <= t; i++) dist[i] = 0; dist[s] = 1, q[l = r = 0] = s; while (l <= r) { int tmp = q[l++]; for (unsigned i = 0; i < a[tmp].size(); i++) if (dist[a[tmp][i].dest] == 0 && a[tmp][i].flow != 0) { dist[a[tmp][i].dest] = dist[tmp] + 1; q[++r] = a[tmp][i].dest; } } return dist[t] != 0; } void addedge(int s, int t, long long x) { a[s].push_back((edge) {t, x, a[t].size()}); a[t].push_back((edge) {s, 0, a[s].size() - 1}); } void addedge(int x, int y, long long l, long long r) { addedge(s, y, l); addedge(x, y, r - l); addedge(x, t, l); } long long f(long long val) { long long diff = 0; s = 0, t = n + 1; for (int i = s; i <= t; i++) a[i].clear(); for (int i = 1; i <= m; i++) { addedge(x[i], y[i], lk[i] * val + lb[i], rk[i] * val + rb[i]); diff += lk[i] * val + lb[i]; } while (bfs()) { memset(curr, 0, sizeof(curr)); diff -= dinic(s, INF); } return diff; } int main() { read(n), read(m); for (int i = 1; i <= m; i++) { read(x[i]), read(y[i]); read(lk[i]), read(lb[i]), lb[i] *= bnd; read(rk[i]), read(rb[i]), rb[i] *= bnd; } long long l = 0, r = bnd; while (l + 5 < r) { long long ml = (2 * l + r) / 3; long long mr = (l + 2 * r) / 3; if (f(ml) < f(mr)) r = mr; else l = ml; } long long mid = l; for (int i = l; i <= r; i++) if (f(i) == 0) mid = i; l = 0, r = mid; while (l < r) { long long md = (l + r) / 2; if (f(md) == 0) r = md; else l = md + 1; } long long ql = l; l = mid, r = 1; while (l < r) { long long md = (l + r + 1) / 2; if (f(md) == 0) l = md; else r = md - 1; } long long qr = l; printf("%.10lf\n", (double) (qr - ql) / bnd); return 0; }