Tarjan 过不了这题吗
查看原帖
Tarjan 过不了这题吗
912750
CarrotMeow楼主2024/7/24 17:10

贡献了 5 发 TLE#7 了。

#pragma GCC optimize(2)
#pragma GCC optimize(3)
#pragma GCC optimize("Ofast")
#pragma GCC optimize("inline")
#pragma GCC optimize("-fgcse")
#pragma GCC optimize("-fgcse-lm")
#pragma GCC optimize("-fipa-sra")
#pragma GCC optimize("-ftree-pre")
#pragma GCC optimize("-ftree-vrp")
#pragma GCC optimize("-fpeephole2")
#pragma GCC optimize("-ffast-math")
#pragma GCC optimize("-fsched-spec")
#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("-falign-jumps")
#pragma GCC optimize("-falign-loops")
#pragma GCC optimize("-falign-labels")
#pragma GCC optimize("-fdevirtualize")
#pragma GCC optimize("-fcaller-saves")
#pragma GCC optimize("-fcrossjumping")
#pragma GCC optimize("-fthread-jumps")
#pragma GCC optimize("-funroll-loops")
#pragma GCC optimize("-freorder-blocks")
#pragma GCC optimize("-fschedule-insns")
#pragma GCC optimize("inline-functions")
#pragma GCC optimize("-ftree-tail-merge")
#pragma GCC optimize("-fschedule-insns2")
#pragma GCC optimize("-fstrict-aliasing")
#pragma GCC optimize("-falign-functions")
#pragma GCC optimize("-fcse-follow-jumps")
#pragma GCC optimize("-fsched-interblock")
#pragma GCC optimize("-fpartial-inlining")
#pragma GCC optimize("no-stack-protector")
#pragma GCC optimize("-freorder-functions")
#pragma GCC optimize("-findirect-inlining")
#pragma GCC optimize("-fhoist-adjacent-loads")
#pragma GCC optimize("-frerun-cse-after-loop")
#pragma GCC optimize("inline-small-functions")
#pragma GCC optimize("-finline-small-functions")
#pragma GCC optimize("-ftree-switch-conversion")
#pragma GCC optimize("-foptimize-sibling-calls")
#pragma GCC optimize("-fexpensive-optimizations")
#pragma GCC optimize("inline-functions-called-once")
#pragma GCC optimize("-fdelete-null-pointer-checks")
#pragma GCC target("sse,sse2,sse3,sse4,popcnt,abm,mmx,avx,avx2")
#include <bits/stdc++.h>
using namespace std;

int read() {
    int x = 0;
    char c = getchar();
    while (!isdigit(c))
        c = getchar();
    while (isdigit(c)) {
        x = x * 10 + c - '0';
        c = getchar();
    }
    return x;
}

const int N = 2e5 + 10;
int n, w[N], u, v, maxd, s;
vector<int> tr[N], tr2[N];

int dfn[N], low[N], top, scc[N], sccn;
bitset<N> instk;
int stktop, stk[N];

void Tarjan(int u) {
    dfn[u] = low[u] = ++top;
    instk[u] = 1;
    stk[++stktop] = u;
    for (int i : tr[u]) {
        if (w[u] != w[i]) continue;
        if (!dfn[i]) {
            Tarjan(i);
            low[u] = min(low[u], low[u]);
        } else if (instk[i])
            low[u] = min(low[u], dfn[i]);
    }
    if (dfn[u] == low[u]) {
        sccn++;
        while (stk[stktop] != u) {
            int v = stk[stktop];
            scc[v] = sccn;
            instk[v] = 0;
            stktop--;
        }
        int v = stk[stktop];
        scc[v] = sccn;
        instk[v] = 0;
        stktop--;
    }
}

void dfs(int u, int fa, int d) {
    if (d > maxd)
        maxd = d, s = u;
    for (int i : tr2[u])
        if (i != fa)
            dfs(i, u, d + 1);
}

signed main() {
    n = read();
    for (int i = 1; i <= n; i++)
        w[i] = read();
    for (int i = 1; i < n; i++) {
        u = read(), v = read();
        tr[u].push_back(v);
        tr[v].push_back(u);
    }

    // for (int i = 1; i <= n; i++)
    //     for (int j : g[i])
    //         cout << i << ' ' << j << '\n';

    for (int i = 1; i <= n; i++)
        if (!dfn[i]) Tarjan(i);
    // for (int i = 1; i <= n; i++)
    //     cout << scc[i] << ' ' << w[i] << '\n';
    // for (int i = 1; i <= sccn; i++)
    //     cout << col[i] << " \n"[i == sccn];

    for (int i = 1; i <= n; i++)
        for (int j : tr[i])
            if (scc[i] != scc[j]) {
                tr2[scc[i]].push_back(scc[j]);
                tr2[scc[j]].push_back(scc[i]);
            }

    dfs(scc[1], 0, 0);
    maxd = 0;
    dfs(s, 0, 0);
    cout << (int)ceil(maxd / 2.0);
}

还是说代码常数过大/kk

2024/7/24 17:10
加载中...