社区讨论

百爪挠心血泪求助,WA第一个点,90pts分

P3854[TJOI2008] 通讯网破坏参与者 4已保存回复 7

讨论操作

快速查看讨论及其快照的属性,并进行相关操作。

当前回复
7 条
当前快照
1 份
快照标识符
@mhj1s9v9
此快照首次捕获于
2025/11/03 19:19
4 个月前
此快照最后确认于
2025/11/03 19:19
4 个月前
查看原帖
CPP
#include <iostream>
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <string>
#include <map>
#include <vector>
#include <queue>
#include <stack>
#include <deque>
#include <set>
using namespace std;

    
template <class T>
string toString(T x) { return to_string(x); }
string toString(const char *x) { return string(x); }
string toString(const string &x) { return x; }
template <class T>
string expand(const T &x) { return toString(x); }
template <class T, class... A>
string expand(const T &x, A... a) { return expand(x) + ", " + expand(a...); }
int read(){int type = 1, n = 0;char ch = getchar();while (ch < '0' || ch > '9'){if (ch == '-'){type = -1;}ch = getchar();}while (ch >= '0' && ch <= '9'){n = (n << 1) + (n << 3) + (ch ^ 48),ch = getchar();}return n * type;}
void write(int n){if (n < 0){putchar('-'), n = -n;}if (n < 10){return putchar(n + '0'), void();}return write(n / 10), putchar(n % 10 + '0'), void();}
void wt(int n, bool o = 1){write(n);if (!o){putchar(' ');}else{putchar('\n');}}

#define debug(a...) cerr << "[" << #a << "] = " << expand(a) << '\n'
#define fileio(x) (freopen(x".in", "r", stdin), freopen(x".out", "w", stdout))
#define rd read()
#define ptc putchar('\n')
#define pii pair<int, int>

const int N = 2e5 + 10;
const int newN = 4e4 + 10;
const int MOD = 998244353;
const int INF = 0x7fffffff;
const int Fill = 0x3f3f3f3f;

int vdcctot, dfscnt, nodetot; // 点双标号,dfs序,圆方树总节点数
int low[N], dfn[N], bel[N], cutId[N]; // bel[i] 是 i属于哪一个点双,cutId是割点的新标号
int fa[newN][23], dep[newN], lg[newN]; // LCA要用的数组
bool cut[N]; // 是否为割点
stack <int> st;
vector <int> G[N], tr[newN], vdcc[N];

void tarjan(int id, int rt) // 常规求点双连通分量,这部分改一改交到模板题过了,大概率没错
{
    int flag = 0;
    if (id == rt && !G[id].size())
    {
        vdcc[++vdcctot].push_back(id);
        return ;
    }
    low[id] = dfn[id] = ++dfscnt;
    st.push(id);
    for (int to : G[id])
    {
        if (!dfn[to])
        {
            tarjan(to, rt);
            low[id] = min(low[id], low[to]);
            if (low[to] >= dfn[id])
            {
                flag++;
                int lst = -1;
                vdcctot++;
                vdcc[vdcctot].push_back(id);
                while (lst != to)
                {
                    lst = st.top();
                    st.pop();
                    vdcc[vdcctot].push_back(lst);
                }
                if (id != rt || flag >= 2)
                {
                    cut[id] = 1;
                }
            }
        }
        else
        {
            low[id] = min(low[id], dfn[to]);
        }
    }
}
void dfs(int id, int from) // LCA预处理
{
    int i;
    dep[id] = dep[from] + 1;
    fa[id][0] = from;
    for (i = 1; i <= lg[dep[id]]; i++)
    {
        fa[id][i] = fa[fa[id][i - 1]][i - 1];
    }
    for (int son : tr[id])
    {
        if (son == from) continue;
        dfs(son, id);
    }
}
int lca(int x, int y) // LCA
{
    int i;
    if (dep[x] < dep[y])
    {
        swap(x, y);
    }
    for (i = 20; i >= 0; i--)
    {
        if (dep[fa[x][i]] >= dep[y])
        {
            x = fa[x][i];
        }
    }
    if (x == y) return x;
    for (i = 20; i >= 0; i--)
    {
        if (fa[x][i] != fa[y][i])
        {
            x = fa[x][i], y = fa[y][i];
        }
    }
    return fa[x][0];
}

void build()
{
    int i, j;
    int n = rd, m = rd;
    for (i = 1; i <= m; i++)
    {
        int x = rd, y = rd;
        G[x].push_back(y), G[y].push_back(x);
    }
    for (i = 1; i <= n; i++)
    {
        if (!dfn[i]) tarjan(i, i);
    }
    lg[1] = 0;
    for (i = 2; i <= newN - 5; i++)
    {
        lg[i] = lg[i >> 1] + 1;
    }
    nodetot = vdcctot;
    for (i = 1; i <= n; i++)
    {
        if (cut[i]) cutId[i] = ++nodetot; // 割点重标号
    }
    for (i = 1; i <= vdcctot; i++)
    {
        for (int node : vdcc[i])
        {
            if (cut[node])
            {
                tr[cutId[node]].push_back(i);
                tr[i].push_back(cutId[node]); // 建圆方树,i是方点,node是圆点
            }
            else
            {
                bel[node] = i;
            }
        }
    }
    dfs(1, 0);
}
int dis(int x, int y)
{
    int anc = lca(x, y);
    // debug(x,y,anc);
    int res = dep[x] + dep[y] - 2 * dep[anc] + 1;
    return res;
}
void solve()
{
    int i, j;
    int s = rd, t = rd, m = rd;
    if (bel[s] == bel[t])
    {
        cout << "no\n";
        return ;
    }
    if (!cut[m])
    {
        cout << "no\n";
        return ;
    }
    if (cut[s]) s = cutId[s];
    else s = bel[s];
    if (cut[t]) t = cutId[t];
    else t = bel[t];
    m = cutId[m];
    int LCA = lca(s, t);
    if (lca(LCA, m) != LCA)
    {
        cout << "no\n";
        return ;
    }
    if (lca(s, m) != m && lca(t, m) != m)
    {
        cout << "no\n";
        return ;
    }
    
    cout << "yes\n";
    return ;
}

signed main()
{
    int T;
    int i, j;
    build();
    T = rd;
    while (T--)
    {
        
        solve();
    }
    return 0;
}
一整天了一直挂第一个点,跪求调题,感激不尽 甚至这个题提交记录里有大量90分

回复

7 条回复,欢迎继续交流。

正在加载回复...