头像

nut96




在线 


最近来访(16)
用户头像
wqwx
用户头像
心影
用户头像
lycckky
用户头像
hrs_Fe_fw
用户头像
T_87
用户头像
runner
用户头像
一半醒
用户头像
大瓜皮
用户头像
阿兔
用户头像
Unique_80
用户头像
H_Freedom
用户头像
peterHUAN

活动打卡代码 AcWing 392. 会合

nut96
1小时前
#include <bits/stdc++.h>
// #define int long long
#define IOS ios::sync_with_stdio(false), cin.tie(0) 
#define ll long long 
#define double long double
#define ull unsigned long long 
#define PII pair<int, int> 
#define PDI pair<double, int> 
#define PDD pair<double, double> 
#define debug(a) cout << #a << " = " << a << endl 
#define point(n) cout << fixed << setprecision(n)
#define all(x) (x).begin(), (x).end() 
#define mem(x, y) memset((x), (y), sizeof(x)) 
#define lbt(x) (x & (-x)) 
#define SZ(x) ((x).size()) 
#define inf 0x3f3f3f3f 
#define INF 0x3f3f3f3f3f3f3f3f
namespace nqio{const unsigned R = 4e5, W = 4e5; char *a, *b, i[R], o[W], *c = o, *d = o + W, h[40], *p = h, y; bool s; struct q{void r(char &x){x = a == b && (b = (a = i) + fread(i, 1, R, stdin), a == b) ? -1 : *a++;} void f(){fwrite(o, 1, c - o, stdout); c = o;} ~q(){f();}void w(char x){*c = x;if (++c == d) f();} q &operator >>(char &x){do r(x);while (x <= 32); return *this;} q &operator >>(char *x){do r(*x); while (*x <= 32); while (*x > 32) r(*++x); *x = 0; return *this;} template<typename t> q&operator>>(t &x){for (r(y),s = 0; !isdigit(y); r(y)) s |= y == 45;if (s) for (x = 0; isdigit(y); r(y)) x = x * 10 - (y ^ 48); else for (x = 0; isdigit(y); r(y)) x = x * 10 + (y ^ 48); return *this;} q &operator <<(char x){w(x);return *this;}q &operator<< (char *x){while (*x) w(*x++); return *this;}q &operator <<(const char *x){while (*x) w(*x++); return *this;}template<typename t> q &operator<< (t x) {if (!x) w(48); else if (x < 0) for (w(45); x; x /= 10) *p++ = 48 | -(x % 10); else for (; x; x /= 10) *p++ = 48 | x % 10; while (p != h) w(*--p);return *this;}}qio; }using nqio::qio;
using namespace std;
const int N = 1e6 + 10, M = 5e5 + 10;
int n, q, nxt[N], pre[N], root;
int h[N], v[N], to[N], tot, f[M][20], cnt, d[M], lg[M], bel[M], pos[M], anc[M], mark[M];
bool vis[M];
vector<int> ring[M];
void add(int a, int b) {
    v[++tot] = b, to[tot] = h[a], h[a] = tot;
}
void dfs(int x, int fa, int depth) {
    bel[x] = cnt, anc[x] = root;
    d[x] = depth;
    f[x][0] = fa;
    vis[x] = 1;
    for (int i = 1; (1ll << i) <= depth; ++i) f[x][i] = f[f[x][i - 1]][i - 1];
    for (int i = h[x]; i; i = to[i]) {
        int y = v[i];
        if (y == fa || mark[y]) continue;
        dfs(y, x, depth + 1);
    }
}
void find(int x) {
    while (!vis[nxt[x]]) vis[x] = 1, pre[nxt[x]] = x, x = nxt[x];
    ++cnt;
    int p = x;
    do {
        mark[p] = 1;
        ring[cnt].emplace_back(p);
        p = pre[p];
    } while (p != nxt[x]);
    mark[p] = 1;
    ring[cnt].emplace_back(p);
    reverse(all(ring[cnt]));
    for (int i = 0; i < ring[cnt].size(); ++i) pos[ring[cnt][i]] = i, root = ring[cnt][i], dfs(ring[cnt][i], -1, 0);
}
int LCA(int x, int y) {
    if (d[x] < d[y]) swap(x, y);
    while (d[x] > d[y]) x = f[x][lg[d[x] - d[y]]];
    if (x == y) return x;
    for (int i = lg[d[x]]; i >= 0; --i)
        if (f[x][i] != f[y][i]) x = f[x][i], y = f[y][i];
    return f[x][0];
}
signed main() {
    qio >> n >> q;
    for (int i = 2; i <= n; ++i) lg[i] = lg[i >> 1] + 1;
    for (int i = 1; i <= n; ++i) {
        qio >> nxt[i];
        add(nxt[i], i);
    }
    for (int i = 1; i <= n; ++i) 
        if (!vis[i]) {
            find(i);
        }
    for (int i = 1; i <= q; ++i) {
        int a, b;
        qio >> a >> b;
        if (bel[a] != bel[b]) qio << -1 << " " << -1 << "\n";
        else {
            if (anc[a] == anc[b]) {
                int lca = LCA(a, b);
                qio << d[a] - d[lca] << " " << d[b] - d[lca] << "\n";
            }else {
                PII choose[3];
                choose[0] = {d[a], d[b] + (pos[anc[a]] - pos[anc[b]] + ring[bel[a]].size()) % (int)ring[bel[a]].size()};
                choose[1] = {d[a] + (pos[anc[b]] - pos[anc[a]] + ring[bel[a]].size()) % (int)ring[bel[a]].size(), d[b]};
                int max0 = max(choose[0].first, choose[0].second), min0 = min(choose[0].first, choose[0].second);
                int max1 = max(choose[1].first, choose[1].second), min1 = min(choose[1].first, choose[1].second);
                int ans = (max0 == max1 ? min0 == min1 ? choose[1].first >= choose[1].second ? 1 : 0 : min0 > min1 ? 1 : 0 : max0 > max1 ? 1 : 0);
                qio << choose[ans].first << " " << choose[ans].second << "\n";
            }
        }
    }
}


活动打卡代码 AcWing 359. 创世纪

nut96
5小时前
#include <bits/stdc++.h>
#define int long long
#define IOS ios::sync_with_stdio(false), cin.tie(0) 
#define ll long long 
#define double long double
#define ull unsigned long long 
#define PII pair<int, int> 
#define PDI pair<double, int> 
#define PDD pair<double, double> 
#define debug(a) cout << #a << " = " << a << endl 
#define point(n) cout << fixed << setprecision(n)
#define all(x) (x).begin(), (x).end() 
#define mem(x, y) memset((x), (y), sizeof(x)) 
#define lbt(x) (x & (-x)) 
#define SZ(x) ((x).size()) 
#define inf 0x3f3f3f3f 
#define INF 0x3f3f3f3f3f3f3f3f
namespace nqio{const unsigned R = 4e5, W = 4e5; char *a, *b, i[R], o[W], *c = o, *d = o + W, h[40], *p = h, y; bool s; struct q{void r(char &x){x = a == b && (b = (a = i) + fread(i, 1, R, stdin), a == b) ? -1 : *a++;} void f(){fwrite(o, 1, c - o, stdout); c = o;} ~q(){f();}void w(char x){*c = x;if (++c == d) f();} q &operator >>(char &x){do r(x);while (x <= 32); return *this;} q &operator >>(char *x){do r(*x); while (*x <= 32); while (*x > 32) r(*++x); *x = 0; return *this;} template<typename t> q&operator>>(t &x){for (r(y),s = 0; !isdigit(y); r(y)) s |= y == 45;if (s) for (x = 0; isdigit(y); r(y)) x = x * 10 - (y ^ 48); else for (x = 0; isdigit(y); r(y)) x = x * 10 + (y ^ 48); return *this;} q &operator <<(char x){w(x);return *this;}q &operator<< (char *x){while (*x) w(*x++); return *this;}q &operator <<(const char *x){while (*x) w(*x++); return *this;}template<typename t> q &operator<< (t x) {if (!x) w(48); else if (x < 0) for (w(45); x; x /= 10) *p++ = 48 | -(x % 10); else for (; x; x /= 10) *p++ = 48 | x % 10; while (p != h) w(*--p);return *this;}}qio; }using nqio::qio;
using namespace std;
//对所有的i->fa[i],最后得到一棵内向树
//在内向树上求最大独立覆盖集,用树形dp
//我们先在内向树上任意选取一点,然后沿着那个点倒着走,遇到环上的一点.
//再把内向树上的边取反,得到外向树,fa[i]是i的父节点
//再断开那个刚才走到的点p和fa[p]的边,此时进行一次树形dp,但是答案还差p与fa[p]的限制
//此时我们强制连接p与fa[p]计算即可

const int N = 2e6 + 10;
int n, fa[N], ring[N], f[N][2], cc, pre[N], uok[N];
int h[N], v[N], to[N], tot = 1, ans, root;
bool vis[N], ok;
void add(int a, int b) {
    v[++tot] = b, to[tot] = h[a], h[a] = tot;
}
void dfs(int x) {
    f[x][1] = f[x][0] = 0;
    vis[x] = 1;
    int del = INF;
    for (int i = h[x], y; i; i = to[i]) {
        y = v[i];
        if (y == root) continue;
        dfs(y);
        f[x][0] += max(f[y][1], f[y][0]);
        del = min(del, max(f[y][0], f[y][1]) - f[y][0]);
    }
    //f[x][1] = f[x][0] - min(max(f[y][0], f[y][1])) + f[y][0]
    f[x][1] = f[x][0] - del + 1;
    if (x == fa[root] && ok) f[x][1] = f[x][0] + 1;
}
void find(int x) {
    root = x;
    while (!vis[fa[root]]) root = fa[root], vis[root] = 1;
}
void work() {
    dfs(root);
    int res = max(f[root][0], f[root][1]);
    ok = 1;
    dfs(root);
    res = max(res, f[root][0]);
    ans += res;
    ok = 0;
}
signed main() {
    qio >> n;
    for (int i = 1; i <= n; ++i) {
        qio >> fa[i];
        add(fa[i], i);
    }
    for (int i = 1; i <= n; ++i) {
        if (!vis[i]) {
            find(i);
            work();
        }
    }
    qio << ans << "\n";

}


活动打卡代码 AcWing 358. 岛屿

nut96
9小时前
#include <bits/stdc++.h>
#define int long long
#define IOS ios::sync_with_stdio(false), cin.tie(0) 
#define ll long long 
#define double long double
#define ull unsigned long long 
#define PII pair<int, int> 
#define PDI pair<double, int> 
#define PDD pair<double, double> 
#define debug(a) cout << #a << " = " << a << endl 
#define point(n) cout << fixed << setprecision(n)
#define all(x) (x).begin(), (x).end() 
#define mem(x, y) memset((x), (y), sizeof(x)) 
#define lbt(x) (x & (-x)) 
#define SZ(x) ((x).size()) 
#define inf 0x3f3f3f3f 
#define INF 0x3f3f3f3f3f3f3f3f
namespace nqio{const unsigned R = 4e5, W = 4e5; char *a, *b, i[R], o[W], *c = o, *d = o + W, h[40], *p = h, y; bool s; struct q{void r(char &x){x = a == b && (b = (a = i) + fread(i, 1, R, stdin), a == b) ? -1 : *a++;} void f(){fwrite(o, 1, c - o, stdout); c = o;} ~q(){f();}void w(char x){*c = x;if (++c == d) f();} q &operator >>(char &x){do r(x);while (x <= 32); return *this;} q &operator >>(char *x){do r(*x); while (*x <= 32); while (*x > 32) r(*++x); *x = 0; return *this;} template<typename t> q&operator>>(t &x){for (r(y),s = 0; !isdigit(y); r(y)) s |= y == 45;if (s) for (x = 0; isdigit(y); r(y)) x = x * 10 - (y ^ 48); else for (x = 0; isdigit(y); r(y)) x = x * 10 + (y ^ 48); return *this;} q &operator <<(char x){w(x);return *this;}q &operator<< (char *x){while (*x) w(*x++); return *this;}q &operator <<(const char *x){while (*x) w(*x++); return *this;}template<typename t> q &operator<< (t x) {if (!x) w(48); else if (x < 0) for (w(45); x; x /= 10) *p++ = 48 | -(x % 10); else for (; x; x /= 10) *p++ = 48 | x % 10; while (p != h) w(*--p);return *this;}}qio; }using nqio::qio;
using namespace std;
const int N = 2e6 + 10;
int n, h[N], v[N], w[N], to[N], tot = 1;
int cc, dd, d[N], prel[N], pre[N], q[N], ans;
bool vis[N], mark[N], ok;
struct {
    int node, val;//val指的是入边的边权
} ring[N];
void add(int a, int b, int c) {
    w[++tot] = c, v[tot] = b, to[tot] = h[a], h[a] = tot;
}
void find(int x, int in_e) {
    vis[x] = 1;
    for (int i = h[x]; i; i = to[i]) {
        int y = v[i];
        if (((in_e ^ 1) == i) || (vis[y] && ok)) continue;
        if (vis[y]) {
            int cur = i ^ 1;
            do {
                ring[++cc] = {v[cur], w[cur]};
                mark[v[cur]] = 1;
                cur = pre[v[cur]];
            } while (v[cur] != y);
            ring[++cc] = {y, w[cur]};
            mark[y] = 1;
            ok = 1;
            continue;
        }
        pre[y] = i ^ 1;
        find(y, i);
    }
}
void dfs(int x, int fa) {
    for (int i = h[x]; i; i = to[i]) {
        int y = v[i];
        if (mark[y] || y == fa) continue;
        dfs(y, x);
        dd = max(dd, d[x] + d[y] + w[i]);
        d[x] = max(d[x], d[y] + w[i]);
    }
}
void work() {
    for (int i = 1; i <= cc; ++i) dfs(ring[i].node, -1), ring[i + cc] = ring[i];
    for (int i = 1; i <= cc * 2; ++i) prel[i] = prel[i - 1] + ring[i].val;
    int l = 1, r = 0;
    for (int i = 1; i <= cc * 2; ++i) {
        int x = ring[i].node;
        while (l <= r && i - q[l] + 1 > cc) ++l;
        if (l <= r) dd = max(dd, d[x] + d[ring[q[l]].node] + prel[i] - prel[q[l]]);
        while (l <= r && d[x] - prel[i] >= d[ring[q[r]].node] - prel[q[r]]) --r;
        q[++r] = i;
    }
    ans += dd;
    dd = cc = 0;
}
signed main() {
    qio >> n;
    for (int i = 1; i <= n; ++i) {
        int a, L;
        qio >> a >> L;
        add(i, a, L), add(a, i, L);
    }
    for (int i = 1; i <= n; ++i)
        if (!vis[i]) {
            ok = 0;
            find(i, 0);
            work();
        }
    qio << ans << "\n";

}


活动打卡代码 AcWing 391. 聚会

nut96
1天前
#include <bits/stdc++.h>
#define int long long
#define IOS ios::sync_with_stdio(false), cin.tie(0) 
#define ll long long 
#define double long double
#define ull unsigned long long 
#define PII pair<int, int> 
#define PDI pair<double, int> 
#define PDD pair<double, double> 
#define debug(a) cout << #a << " = " << a << endl 
#define point(n) cout << fixed << setprecision(n)
#define all(x) (x).begin(), (x).end() 
#define mem(x, y) memset((x), (y), sizeof(x)) 
#define lbt(x) (x & (-x)) 
#define SZ(x) ((x).size()) 
#define inf 0x3f3f3f3f 
#define INF 0x3f3f3f3f3f3f3f3f
namespace nqio{const unsigned R = 4e5, W = 4e5; char *a, *b, i[R], o[W], *c = o, *d = o + W, h[40], *p = h, y; bool s; struct q{void r(char &x){x = a == b && (b = (a = i) + fread(i, 1, R, stdin), a == b) ? -1 : *a++;} void f(){fwrite(o, 1, c - o, stdout); c = o;} ~q(){f();}void w(char x){*c = x;if (++c == d) f();} q &operator >>(char &x){do r(x);while (x <= 32); return *this;} q &operator >>(char *x){do r(*x); while (*x <= 32); while (*x > 32) r(*++x); *x = 0; return *this;} template<typename t> q&operator>>(t &x){for (r(y),s = 0; !isdigit(y); r(y)) s |= y == 45;if (s) for (x = 0; isdigit(y); r(y)) x = x * 10 - (y ^ 48); else for (x = 0; isdigit(y); r(y)) x = x * 10 + (y ^ 48); return *this;} q &operator <<(char x){w(x);return *this;}q &operator<< (char *x){while (*x) w(*x++); return *this;}q &operator <<(const char *x){while (*x) w(*x++); return *this;}template<typename t> q &operator<< (t x) {if (!x) w(48); else if (x < 0) for (w(45); x; x /= 10) *p++ = 48 | -(x % 10); else for (; x; x /= 10) *p++ = 48 | x % 10; while (p != h) w(*--p);return *this;}}qio; }using nqio::qio;
using namespace std;
const int N = 1e6 + 10;
int n, m;
int h[N], v[N], to[N], tot;
int dep[N], f[N][22], d[N], lg[N];
void add(int a, int b) {
    v[++tot] = b, to[tot] = h[a], h[a] = tot;
}
void dfs(int x, int fa, int depth) {
    f[x][0] = fa, dep[x] = depth;
    for (int i = 1; i <= 20; ++i) f[x][i] = f[f[x][i - 1]][i - 1];
    for (int i = h[x], y; i; i = to[i]) {
        if ((y = v[i]) == fa) continue;
        d[y] = d[x] + 1;
        dfs(y, x, depth + 1);
    }
}
int lca(int x, int y) {
    if (dep[x] < dep[y]) swap(x, y);
    while (dep[x] > dep[y]) x = f[x][lg[dep[x] - dep[y]]];
    if (x == y) return x;
    for (int i = lg[dep[x]]; i >= 0; --i) if (f[x][i] != f[y][i]) x = f[x][i], y = f[y][i];
    return f[x][0];
}
int dist(int a, int b) {
    return d[a] + d[b] - 2 * d[lca(a, b)];
}
signed main() {
    qio >> n >> m;
    for (int i = 2; i <= 1e6; ++i) lg[i] = lg[i >> 1] + 1;
    for (int i = 1; i <= n - 1; ++i) {
        int x, y;
        qio >> x >> y;
        add(x, y), add(y, x);
    }
    dfs(1, 0, 1);
    for (int i = 1, a, b, c; i <= m; ++i) {
        qio >> a >> b >> c;
        int id, val = INF, t1, t2;
        if ((t1 = dist(a, b) + dist(c, t2 = lca(a, b))) < val) val = t1, id = t2;
        if ((t1 = dist(a, c) + dist(b, t2 = lca(a, c))) < val) val = t1, id = t2;
        if ((t1 = dist(b, c) + dist(a, t2 = lca(b, c))) < val) val = t1, id = t2;
        qio << id << " " << val << "\n";
    }
}


活动打卡代码 AcWing 355. 异象石

nut96
4天前
#include <bits/stdc++.h>
#define int long long
#define IOS ios::sync_with_stdio(false), cin.tie(0) 
#define ll long long 
#define double long double
#define ull unsigned long long 
#define PII pair<int, int> 
#define PDI pair<double, int> 
#define PDD pair<double, double> 
#define debug(a) cout << #a << " = " << a << endl 
#define point(n) cout << fixed << setprecision(n)
#define all(x) (x).begin(), (x).end() 
#define mem(x, y) memset((x), (y), sizeof(x)) 
#define lbt(x) (x & (-x)) 
#define SZ(x) ((x).size()) 
#define inf 0x3f3f3f3f 
#define INF 0x3f3f3f3f3f3f3f3f
namespace nqio{const unsigned R = 4e5, W = 4e5; char *a, *b, i[R], o[W], *c = o, *d = o + W, h[40], *p = h, y; bool s; struct q{void r(char &x){x = a == b && (b = (a = i) + fread(i, 1, R, stdin), a == b) ? -1 : *a++;} void f(){fwrite(o, 1, c - o, stdout); c = o;} ~q(){f();}void w(char x){*c = x;if (++c == d) f();} q &operator >>(char &x){do r(x);while (x <= 32); return *this;} q &operator >>(char *x){do r(*x); while (*x <= 32); while (*x > 32) r(*++x); *x = 0; return *this;} template<typename t> q&operator>>(t &x){for (r(y),s = 0; !isdigit(y); r(y)) s |= y == 45;if (s) for (x = 0; isdigit(y); r(y)) x = x * 10 - (y ^ 48); else for (x = 0; isdigit(y); r(y)) x = x * 10 + (y ^ 48); return *this;} q &operator <<(char x){w(x);return *this;}q &operator<< (char *x){while (*x) w(*x++); return *this;}q &operator <<(const char *x){while (*x) w(*x++); return *this;}template<typename t> q &operator<< (t x) {if (!x) w(48); else if (x < 0) for (w(45); x; x /= 10) *p++ = 48 | -(x % 10); else for (; x; x /= 10) *p++ = 48 | x % 10; while (p != h) w(*--p);return *this;}}qio; }using nqio::qio;
using namespace std;

//我们让现有的异象石构成一棵生成树,然后给原树打dfn序
//然后生成树中所有dfn序相邻的边对树进行覆盖,刚好是答案的两倍
//此时我们考虑增加一个点带来的影响,对于一个新增加的点x,会对相邻的dfn序的两个点产生影响,假设为l,r
//res = res - dist(l, r) + dist(l, x), + dist(r, x)
const int N = 2e6 + 10;
int n, q, h[N], v[N], w[N], to[N], tot;
int tpf[N], fa[N], sz[N], son[N], dep[N], dfn[N], tim, d[N];
set<PII> s; 
void add(int a, int b, int c) {
    w[++tot] = c, v[tot] = b, to[tot] = h[a], h[a] = tot;
}
void dfs1(int x, int f, int depth) {
    dep[x] = depth; fa[x] = f, sz[x] = 1;
    int mxsz = -1;
    for (int i = h[x], y; i; i = to[i]) {
        if ((y = v[i]) == f) continue;
        d[y] = d[x] + w[i];
        dfs1(y, x, depth + 1);
        sz[x] += sz[y];
        if (mxsz < sz[y]) mxsz = sz[y], son[x] = y;
    }
}
void dfs2(int x, int topf) {
    dfn[x] = ++tim, tpf[x] = topf;
    if (!son[x]) return;
    dfs2(son[x], topf);
    for (int i = h[x], y; i; i = to[i]) {
        if ((y = v[i]) == fa[x] || y == son[x]) continue;
        dfs2(y, y);
    }
}
int dist(int x, int y) {
    int xx = x, yy = y;
    while (tpf[x] != tpf[y]) {
        if (dep[tpf[x]] < dep[tpf[y]]) swap(x, y);
        x = fa[tpf[x]];
    }
    if (dep[x] > dep[y]) swap(x, y);
    return d[xx] + d[yy] - 2 * d[x];
}
signed main() {
    qio >> n;
    for (int i = 1; i <= n - 1; ++i) {
        int x, y, z;
        qio >> x >> y >> z;
        add(x, y, z), add(y, x, z);
    }
    dfs1(1, -1, 1), dfs2(1, 1);
    int res = 0;
    qio >> q;
    for (int i = 1; i <= q; ++i) {
        char op[2];
        int x;
        qio >> op;
        if (op[0] == '+') {
            qio >> x;   
            if (s.empty()) s.emplace(dfn[x], x);
            else {
                auto l = --s.lower_bound({dfn[x], x}), r = s.lower_bound({dfn[x], x});
                if (r == s.begin()) l = --s.end();
                if (r == s.end())   r = s.begin();
                res = res - dist(l->second, r->second) + dist(x, l->second) + dist(x, r->second);
                s.emplace(dfn[x], x);
            }
        }else if (op[0] == '-') {
            qio >> x;
            s.erase({dfn[x], x});
            if (s.empty()) continue;
            auto l = --s.lower_bound({dfn[x], x}), r = s.lower_bound({dfn[x], x});
            if (r == s.begin()) l = --s.end();
            if (r == s.end())   r = s.begin();
            res = res + dist(l->second, r->second) - dist(x, l->second) - dist(x, r->second);
        }else qio << res / 2 << "\n";
    }
}


活动打卡代码 AcWing 389. 直径

nut96
4天前
#include <bits/stdc++.h>
#define int long long
#define IOS ios::sync_with_stdio(false), cin.tie(0) 
#define ll long long 
#define double long double
#define ull unsigned long long 
#define PII pair<int, int> 
#define PDI pair<double, int> 
#define PDD pair<double, double> 
#define debug(a) cout << #a << " = " << a << endl 
#define point(n) cout << fixed << setprecision(n)
#define all(x) (x).begin(), (x).end() 
#define mem(x, y) memset((x), (y), sizeof(x)) 
#define lbt(x) (x & (-x)) 
#define SZ(x) ((x).size()) 
#define inf 0x3f3f3f3f 
#define INF 0x3f3f3f3f3f3f3f3f
namespace nqio{const unsigned R = 4e5, W = 4e5; char *a, *b, i[R], o[W], *c = o, *d = o + W, h[40], *p = h, y; bool s; struct q{void r(char &x){x = a == b && (b = (a = i) + fread(i, 1, R, stdin), a == b) ? -1 : *a++;} void f(){fwrite(o, 1, c - o, stdout); c = o;} ~q(){f();}void w(char x){*c = x;if (++c == d) f();} q &operator >>(char &x){do r(x);while (x <= 32); return *this;} q &operator >>(char *x){do r(*x); while (*x <= 32); while (*x > 32) r(*++x); *x = 0; return *this;} template<typename t> q&operator>>(t &x){for (r(y),s = 0; !isdigit(y); r(y)) s |= y == 45;if (s) for (x = 0; isdigit(y); r(y)) x = x * 10 - (y ^ 48); else for (x = 0; isdigit(y); r(y)) x = x * 10 + (y ^ 48); return *this;} q &operator <<(char x){w(x);return *this;}q &operator<< (char *x){while (*x) w(*x++); return *this;}q &operator <<(const char *x){while (*x) w(*x++); return *this;}template<typename t> q &operator<< (t x) {if (!x) w(48); else if (x < 0) for (w(45); x; x /= 10) *p++ = 48 | -(x % 10); else for (; x; x /= 10) *p++ = 48 | x % 10; while (p != h) w(*--p);return *this;}}qio; }using nqio::qio;
using namespace std;
const int N = 2e6 + 10;
int n, h[N], v[N], w[N], to[N], tot = 1, d[N], pre[N], path[N], m, maxd[N], cnt[N];
void add(int a, int b, int c) {
    w[++tot] = c, v[tot] = b, to[tot] = h[a], h[a] = tot;
}
PII bfs(int S) {
    for (int i = 1; i <= n; ++i) d[i] = -1;
    queue<int> q;
    q.emplace(S), d[S] = 0;
    while (q.size()) {
        int x = q.front(); q.pop();
        for (int i = h[x], y; i; i = to[i]) {
            if (d[y = v[i]] != -1) continue;
            d[y] = d[x] + w[i];
            pre[y] = i;
            q.emplace(y);
        }
    }
    int ans = 0, id;
    for (int i = 1; i <= n; ++i)
        if (d[i] > ans) {
            ans = d[i];
            id = i;
        }
    return {ans, id};
}
void dfs(int x, int fa) {
    int leaf = 1, cc = 0, mx = 0;
    for (int i = h[x], y; i; i = to[i]) {
        if ((y = v[i]) == fa) continue;
        leaf = 0;
        dfs(y, x);
        if (mx < maxd[y] + w[i])
            mx = maxd[y] + w[i], cc = cnt[y];
        else if (mx == maxd[y] + w[i])
            cc += cnt[y];
    }
    if (leaf) maxd[x] = 0, cnt[x] = 1;
    else maxd[x] = mx, cnt[x] = cc;
}
signed main() {
    qio >> n;
    for (int i = 1; i <= n - 1; ++i) {
        int a, b, c;
        qio >> a >> b >> c;
        add(a, b, c), add(b, a, c);
    }
    int st;
    auto [len, ed] = bfs(st = bfs(1).second);
    int x = ed, now = 0;    
    while (x != st) {
        path[++m] = x;
        int i = pre[x];
        x = v[i ^ 1];
    }
    path[++m] = st;
    // qio << st << " " << ed << "\n";
    dfs(st, -1);
    int u = m, v = 1;
    for (int i = 2; i <= m; ++i)
        if (cnt[path[i - 1]] < cnt[path[i]])
            v = i;
    // qio << v << "\n";
    for (int i = 1; i <= n; ++i) maxd[i] = 0, cnt[i] = 0;
    dfs(ed, -1);
    // for (int i = 1; i <= n; ++i) qio << maxd[i] << " " << cnt[i] << "\n";
    for (int i = m - 1; i >= 1; --i)
        if (cnt[path[i + 1]] < cnt[path[i]])
            u = i;
    qio << len << "\n" << abs(u - v) << "\n";

}


活动打卡代码 AcWing 390. 逃学的小孩

nut96
4天前
#include <bits/stdc++.h>
#define int long long
#define IOS ios::sync_with_stdio(false), cin.tie(0) 
#define ll long long 
#define double long double
#define ull unsigned long long 
#define PII pair<int, int> 
#define PDI pair<double, int> 
#define PDD pair<double, double> 
#define debug(a) cout << #a << " = " << a << endl 
#define point(n) cout << fixed << setprecision(n)
#define all(x) (x).begin(), (x).end() 
#define mem(x, y) memset((x), (y), sizeof(x)) 
#define lbt(x) (x & (-x)) 
#define SZ(x) ((x).size()) 
#define inf 0x3f3f3f3f 
#define INF 0x3f3f3f3f3f3f3f3f
namespace nqio{const unsigned R = 4e5, W = 4e5; char *a, *b, i[R], o[W], *c = o, *d = o + W, h[40], *p = h, y; bool s; struct q{void r(char &x){x = a == b && (b = (a = i) + fread(i, 1, R, stdin), a == b) ? -1 : *a++;} void f(){fwrite(o, 1, c - o, stdout); c = o;} ~q(){f();}void w(char x){*c = x;if (++c == d) f();} q &operator >>(char &x){do r(x);while (x <= 32); return *this;} q &operator >>(char *x){do r(*x); while (*x <= 32); while (*x > 32) r(*++x); *x = 0; return *this;} template<typename t> q&operator>>(t &x){for (r(y),s = 0; !isdigit(y); r(y)) s |= y == 45;if (s) for (x = 0; isdigit(y); r(y)) x = x * 10 - (y ^ 48); else for (x = 0; isdigit(y); r(y)) x = x * 10 + (y ^ 48); return *this;} q &operator <<(char x){w(x);return *this;}q &operator<< (char *x){while (*x) w(*x++); return *this;}q &operator <<(const char *x){while (*x) w(*x++); return *this;}template<typename t> q &operator<< (t x) {if (!x) w(48); else if (x < 0) for (w(45); x; x /= 10) *p++ = 48 | -(x % 10); else for (; x; x /= 10) *p++ = 48 | x % 10; while (p != h) w(*--p);return *this;}}qio; }using nqio::qio;
using namespace std;
const int N = 2e6 + 10;
int n, h[N], v[N], w[N], to[N], tot = 1, d[N], k[N], pre[N], path[N], m, sum[N];
void add(int a, int b, int c) {
    w[++tot] = c, v[tot] = b, to[tot] = h[a], h[a] = tot;
}
PII bfs(int S) {
    for (int i = 1; i <= n; ++i) d[i] = -1;
    queue<int> q;
    q.emplace(S), d[S] = 0;
    while (q.size()) {
        int x = q.front(); q.pop();
        for (int i = h[x], y; i; i = to[i]) {
            if (d[y = v[i]] != -1) continue;
            d[y] = d[x] + w[i];
            pre[y] = i;
            q.emplace(y);
        }
    }
    int ans = 0, id;
    for (int i = 1; i <= n; ++i)
        if (d[i] > ans) {
            ans = d[i];
            id = i;
        }
    return {ans, id};
}
signed main() {
    int tt;
    qio >> n >> tt;
    for (int i = 1; i <= n - 1; ++i) {
        int a, b, c;
        qio >> a >> b >> c;
        add(a, b, c), add(b, a, c);
    }
    int st;
    auto [len, ed] = bfs(st = bfs(1).second);
    for (int i = 1; i <= n; ++i) k[i] = d[i];
    bfs(ed);
    int mx = 0;
    for (int i = 1; i <= n; ++i) mx = max(mx, min(d[i], k[i]));
    qio << len + mx << "\n";
}


活动打卡代码 AcWing 382. K取方格数

nut96
19天前
#include <bits/stdc++.h>
#define int long long
#define IOS ios::sync_with_stdio(false), cin.tie(0) 
#define ll long long 
#define ull unsigned long long 
#define PII pair<int, int> 
#define PDI pair<double, int> 
#define PDD pair<double, double> 
#define debug(a) cout << #a << " = " << a << endl 
#define all(x) (x).begin(), (x).end() 
#define mem(x, y) memset((x), (y), sizeof(x)) 
#define lbt(x) (x & (-x)) 
#define SZ(x) ((x).size()) 
#define inf 0x3f3f3f3f 
#define INF 0x3f3f3f3f3f3f3f3f
namespace nqio{const unsigned R = 4e5, W = 4e5; char *a, *b, i[R], o[W], *c = o, *d = o + W, h[40], *p = h, y; bool s; struct q{void r(char &x){x = a == b && (b = (a = i) + fread(i, 1, R, stdin), a == b) ? -1 : *a++;} void f(){fwrite(o, 1, c - o, stdout); c = o;} ~q(){f();}void w(char x){*c = x;if (++c == d) f();} q &operator >>(char &x){do r(x);while (x <= 32); return *this;} q &operator >>(char *x){do r(*x); while (*x <= 32); while (*x > 32) r(*++x); *x = 0; return *this;} template<typename t> q&operator>>(t &x){for (r(y),s = 0; !isdigit(y); r(y)) s |= y == 45;if (s) for (x = 0; isdigit(y); r(y)) x = x * 10 - (y ^ 48); else for (x = 0; isdigit(y); r(y)) x = x * 10 + (y ^ 48); return *this;} q &operator <<(char x){w(x);return *this;}q &operator<< (char *x){while (*x) w(*x++); return *this;}q &operator <<(const char *x){while (*x) w(*x++); return *this;}template<typename t> q &operator<< (t x) {if (!x) w(48); else if (x < 0) for (w(45); x; x /= 10) *p++ = 48 | -(x % 10); else for (; x; x /= 10) *p++ = 48 | x % 10; while (p != h) w(*--p);return *this;}}qio; }using nqio::qio;
using namespace std;
const int N = 5010, M = 2e5 + 10;
int n, k, S, T, ans;
int h[N], v[M], to[M], w[M],/*容量*/ cost[M],/*费用*/ tot;
int maxflow, d[N], vis[N], incf[N], /*表示当前点的最大流*/pre[N];/*前驱*/
void add(int a, int b, int c, int z) {
    cost[++tot] = z, w[tot] = c, v[tot] = b, to[tot] = h[a], h[a] = tot;
    cost[++tot] = -z,w[tot] = 0, v[tot] = a, to[tot] = h[b], h[b] = tot;
}
int calc(int x, int y, int tp) {return (x - 1) * n + y + tp * n * n;}
bool spfa() {
    queue<int> q;
    mem(d, 0xcf), mem(vis, 0);
    q.emplace(S), d[S] = 0, vis[S] = 1;
    incf[S] = INF;
    while (q.size()) {
        int x = q.front(); q.pop(); vis[x] = 0;
        for (int i = h[x], y, z; i; i = to[i]) {
            if (!(z = w[i])) continue;/*不在残量网络中*/
            if (d[y = v[i]] < d[x] + cost[i]) {
                d[y] = d[x] + cost[i];
                incf[y] = min(incf[x], z);
                pre[y] = i; /*记录前驱,便于找到最长路的实际方案*/
                if (!vis[y]) vis[y] = 1, q.emplace(y);
            }
        }
    }
    if (d[T] == 0xcfcfcfcfcfcfcfcf) return false; //汇点不可达,已求出最大流
    return true;
}
void update() {
    int x = T;
    while (x != S) {
        int i = pre[x];
        w[i] -= incf[T];
        w[i ^ 1] += incf[T];
        x = v[i ^ 1];
    }
    maxflow += incf[T];
    ans += d[T] * incf[T];
}
signed main() { 
    qio >> n >> k;
    tot = 1, S = 1, T = 2 * n * n;
    for (int i = 1; i <= n; ++i) 
        for (int j = 1; j <= n; ++j) {
            int c; qio >> c;
            add(calc(i, j, 0), calc(i, j, 1), 1, c); //方格内,拆成出点和入点,点出->点入 = (1(容量),c(费用,方格内的数)),(k-1,0),相邻格子=(k,0)
            add(calc(i, j, 0), calc(i, j, 1), k - 1, 0);
            if (j < n) add(calc(i, j, 1), calc(i, j + 1, 0), k, 0);
            if (i < n) add(calc(i, j, 1), calc(i + 1, j, 0), k, 0);
        }
    while (spfa()) update();
    qio << ans << "\n";
}


活动打卡代码 AcWing 368. 银河

nut96
19天前
#include <bits/stdc++.h>
#define int long long
#define IOS ios::sync_with_stdio(false), cin.tie(0) 
#define ll long long 
#define ull unsigned long long 
#define PII pair<int, int> 
#define PDI pair<double, int> 
#define PDD pair<double, double> 
#define debug(a) cout << #a << " = " << a << endl 
#define all(x) (x).begin(), (x).end() 
#define mem(x, y) memset((x), (y), sizeof(x)) 
#define lbt(x) (x & (-x)) 
#define SZ(x) ((x).size()) 
#define inf 0x3f3f3f3f 
#define INF 0x3f3f3f3f3f3f3f3f
namespace nqio{const unsigned R = 4e5, W = 4e5; char *a, *b, i[R], o[W], *c = o, *d = o + W, h[40], *p = h, y; bool s; struct q{void r(char &x){x = a == b && (b = (a = i) + fread(i, 1, R, stdin), a == b) ? -1 : *a++;} void f(){fwrite(o, 1, c - o, stdout); c = o;} ~q(){f();}void w(char x){*c = x;if (++c == d) f();} q &operator >>(char &x){do r(x);while (x <= 32); return *this;} q &operator >>(char *x){do r(*x); while (*x <= 32); while (*x > 32) r(*++x); *x = 0; return *this;} template<typename t> q&operator>>(t &x){for (r(y),s = 0; !isdigit(y); r(y)) s |= y == 45;if (s) for (x = 0; isdigit(y); r(y)) x = x * 10 - (y ^ 48); else for (x = 0; isdigit(y); r(y)) x = x * 10 + (y ^ 48); return *this;} q &operator <<(char x){w(x);return *this;}q &operator<< (char *x){while (*x) w(*x++); return *this;}q &operator <<(const char *x){while (*x) w(*x++); return *this;}template<typename t> q &operator<< (t x) {if (!x) w(48); else if (x < 0) for (w(45); x; x /= 10) *p++ = 48 | -(x % 10); else for (; x; x /= 10) *p++ = 48 | x % 10; while (p != h) w(*--p);return *this;}}qio; }using nqio::qio;
using namespace std;
const int N = 2e6 + 10, M = 1e5 + 10; 
int n, m;
int h[N], to[N], tot, v[N], w[N];
int hc[N], toc[N], tc, vc[N], wc[N];
int dfn[N], low[N], tim, c[N], cnt, instk[N];
int in[N], f[N];
vector<int> stk, scc[M];//注意这个不要开太大,会mle
void add(int a, int b, int c) {w[++tot] = c, v[tot] = b, to[tot] = h[a], h[a] = tot;}
void add_c(int a, int b, int c) {wc[++tc] = c, vc[tc] = b, toc[tc] = hc[a], hc[a] = tc;}
//--------------------------------------------------------------------------------
void tarjan(int x) {
    dfn[x] = low[x] = ++tim;
    stk.emplace_back(x); instk[x] = 1;
    for (int i = h[x], y; i; i = to[i]) 
        if (!dfn[y = v[i]]) {
            tarjan(y);
            low[x] = min(low[x], low[y]);
        }else if (instk[y]) low[x] = min(low[x], dfn[y]);
    if (dfn[x] == low[x]) {
        ++cnt; int y;
        do {
            y = stk.back(); stk.pop_back();/*记得要出栈*/ instk[y] = 0;
            c[y] = cnt; scc[cnt].emplace_back(y);
        } while (x != y);
    }
}
//--------------------------------------------------------------------------------
signed main() {
    qio >> n >> m;
    for (int i = 1; i <= m; ++i) {
        int t, a, b;
        qio >> t >> a >> b;
        if (t == 1) add(a, b, 0), add(b, a, 0);
        else if (t == 2) add(a, b, 1);
        else if (t == 3) add(b, a, 0);
        else if (t == 4) add(b, a, 1);
        else if (t == 5) add(a, b, 0);
    }
    for (int i = 1; i <= n; ++i) add(0, i, 1);
    //求dcc+缩点
    for (int i = 0; i <= n; ++i) if (!dfn[i]) tarjan(i);
    for (int x = 0; x <= n; ++x) 
        for (int i = h[x]; i; i = to[i]) {
            int y = v[i];
            if (c[x] == c[y]) {
                if (w[i] > 0) return qio << "-1\n", 0;
            }else add_c(c[x], c[y], w[i]);
        }
    //注意,根据tarjan算法的特点,强连通分量的标号是刚好逆着拓扑序的,也就是说,我们从最大的强连通分量的编号求到最小的编号就是拓扑序了
    for (int x = cnt; x; --x) for (int i = hc[x]; i; i = toc[i]) {
        int y = vc[i], z = wc[i];
        f[y] = max(f[y], f[x] + z);
    }
    int ans = 0;
    for (int i = 1; i <= cnt; ++i) ans += f[i] * SZ(scc[i]);
    qio << ans << "\n";
}


活动打卡代码 AcWing 381. 有线电视网络

nut96
19天前
#include <bits/stdc++.h>
#define int long long
#define IOS ios::sync_with_stdio(false), cin.tie(0) 
#define ll long long 
#define ull unsigned long long 
#define PII pair<int, int> 
#define PDI pair<double, int> 
#define PDD pair<double, double> 
#define debug(a) cout << #a << " = " << a << endl 
#define all(x) (x).begin(), (x).end() 
#define mem(x, y) memset((x), (y), sizeof(x)) 
#define lbt(x) (x & (-x)) 
#define SZ(x) ((x).size()) 
#define inf 0x3f3f3f3f 
#define INF 0x3f3f3f3f3f3f3f3f
// namespace nqio{const unsigned R = 4e5, W = 4e5; char *a, *b, i[R], o[W], *c = o, *d = o + W, h[40], *p = h, y; bool s; struct q{void r(char &x){x = a == b && (b = (a = i) + fread(i, 1, R, stdin), a == b) ? -1 : *a++;} void f(){fwrite(o, 1, c - o, stdout); c = o;} ~q(){f();}void w(char x){*c = x;if (++c == d) f();} q &operator >>(char &x){do r(x);while (x <= 32); return *this;} q &operator >>(char *x){do r(*x); while (*x <= 32); while (*x > 32) r(*++x); *x = 0; return *this;} template<typename t> q&operator>>(t &x){for (r(y),s = 0; !isdigit(y); r(y)) s |= y == 45;if (s) for (x = 0; isdigit(y); r(y)) x = x * 10 - (y ^ 48); else for (x = 0; isdigit(y); r(y)) x = x * 10 + (y ^ 48); return *this;} q &operator <<(char x){w(x);return *this;}q &operator<< (char *x){while (*x) w(*x++); return *this;}q &operator <<(const char *x){while (*x) w(*x++); return *this;}template<typename t> q &operator<< (t x) {if (!x) w(48); else if (x < 0) for (w(45); x; x /= 10) *p++ = 48 | -(x % 10); else for (; x; x /= 10) *p++ = 48 | x % 10; while (p != h) w(*--p);return *this;}}qio; }using nqio::qio;
using namespace std;
const int N = 510, M = 1e4 + 5;
int n, m;
int h[N], v[M], to[M], w[M], tot, d[N], S, T, now[N], we[M];
void add(int a, int b, int c) {
    w[++tot] = c, v[tot] = b, to[tot] = h[a], h[a] = tot;
    w[++tot] = 0, v[tot] = a, to[tot] = h[b], h[b] = tot;
}
bool bfs() {
    mem(d, 0);
    queue<int> q;
    q.emplace(S); d[S] = 1; now[S] = h[S];
    while (q.size()) {
        int x = q.front(); q.pop();
        for (int i = h[x], y; i; i = to[i]) 
            if (w[i] && !d[y = v[i]]) {
                q.emplace(y);
                now[y] = h[y];
                d[y] = d[x] + 1;
                if (y == T) return true;
            }
    }
    return false;
}
int dinic(int x, int flow) {
    if (x == T) return flow;
    int rest = flow, k;
    for (int i = now[x], y; i && rest; i = to[i]) {
        now[x] = i;
        if (w[i] && d[y = v[i]] == d[x] + 1) {
            k = dinic(y, min(rest, w[i]));
            if (!k) d[y] = 0;
            w[i] -= k;
            w[i ^ 1] += k;
            rest -= k;
        }
    }
    return flow - rest;
}
signed main() { 
    while (scanf("%lld%lld",&n, &m) == 2) {
        for (int i = 1; i <= n * 2; ++i) h[i] = 0; tot = 1;
        for (int i = 1; i <= m; ++i) {
            char c;
            int x, y;
            cin >> c;
            scanf("%lld,%lld", &x, &y);
            // debug(x), debug(y);
            cin >> c;
            ++x, ++y;
            // cout << x << " " << y << "\n";
            add(x, y + n, 0); //入->出 = 0 一定会被割断,因为这条边本来就不在
            add(y, x + n, 0);
            add(x + n, y, INF); //出->入 = inf 防止割断
            add(y + n, x, INF);
        }
        for (int i = 1; i <= n; ++i) add(i, i + n, 1), add(i + n, i, 0); //点入->点出 = 1 最大流=最小割
        int ans = n, maxflow, flow;
        memcpy(we, w, sizeof w);
        //先枚举终点S'(出点),再枚举起点T(终点)
        for (S = n + 1; S <= n * 2; ++S)
            for (T = S - n + 1; T <= n; ++T) {
                memcpy(w, we, sizeof we);
                maxflow = flow = 0;
                while (bfs()) while (flow = dinic(S, INF)) maxflow += flow;
                ans = min(ans, maxflow);
            }
        printf("%lld\n", ans);
    }
}