建议加强此题数据

如题，蒟蒻过了这道题，但是去写了一发Codeforces 757F这道题（虽然实际上是DAG但是我写的是一般图支配树），一直TLE，后来发现是每次通过fa更新idom结束之后应当清空fa的邻接表，以保证时间复杂度不退化为

O(n^2)

.但是我的这个错误模板在洛谷依然能够通过，而且貌似洛谷的某些题解也是

O(n^2)

的。因此强烈建议加强本题数据卡掉这些不合格代码。（但是由于我很菜不会造数据……QAQ）

附代码

CPP

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cassert>
#define llong long long
using namespace std;

const int N = 2e5;
const int M = 3e5;
struct Edge
{
    int v,nxt;
} e[(M<<1)+3],ei[(M<<1)+3],e1[(M<<1)+3],e0[(M<<1)+3];
int fe[N+3],fei[N+3],fe1[N+3],fe0[N+3];
int sdom[N+3],idom[N+3];
int uf[N+3],mnuf[N+3];
int dfn[N+3],idfn[N+3];
int fa[N+3];
int sz0[N+3];
int n,m,en,eni,en1,en0,cnt;

void addedge(Edge _e[],int &_en,int _fe[],int u,int v)
{
    _en++; _e[_en].v = v;
    _e[_en].nxt = _fe[u]; _fe[u] = _en;
}

void dfs(int u)
{
    cnt++; dfn[u] = cnt; idfn[cnt] = u;
    for(int i=fe[u]; i; i=e[i].nxt)
    {
        if(!dfn[e[i].v]) {fa[e[i].v] = u; dfs(e[i].v);}
    }
}

int findfa(int u)
{
    if(u==uf[u]) return u;
    int v = u;
    int x = findfa(uf[u]); u = uf[u];
    mnuf[v] = dfn[sdom[mnuf[v]]]<dfn[sdom[mnuf[u]]] ? mnuf[v] : mnuf[u];
    uf[v] = x;
    return u;
}

void mergefa(int u,int v)
{
    uf[v] = u;
}

void dfs0(int u)
{
    sz0[u] = 1;
    for(int i=fe0[u]; i; i=e0[i].nxt)
    {
        dfs0(e0[i].v);
        sz0[u] += sz0[e0[i].v];
    }
}

int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1; i<=n; i++) sdom[i] = uf[i] = mnuf[i] = i;
    for(int i=1; i<=m; i++)
    {
        int x,y; scanf("%d%d",&x,&y); addedge(e,en,fe,x,y); addedge(ei,eni,fei,y,x);
    }
    cnt = 0; dfs(1);
    for(int i=cnt; i>=2; i--)
    {
        int u = idfn[i];
        for(int j=fei[u]; j; j=ei[j].nxt)
        {
            int v = ei[j].v;
            if(!dfn[v]) continue;
            findfa(v);
            if(dfn[sdom[mnuf[v]]]<dfn[sdom[u]])
            {
                sdom[u] = sdom[mnuf[v]];
            }
        }
        addedge(e1,en1,fe1,sdom[u],u);
        mergefa(fa[u],u);
        u = fa[u];
        for(int j=fe1[u]; j; j=e1[j].nxt)
        {
            int v = e1[j].v;
            findfa(v);
            if(sdom[mnuf[v]]==u) {idom[v] = u; assert(sdom[v]==u);}
            else {idom[v] = mnuf[v];}
        }
        fe1[u] = 0; //TLE on Codeforces 757F without this line
    }
    for(int i=2; i<=cnt; i++)
    {
        int u = idfn[i];
        if(idom[u]!=sdom[u]) {idom[u] = idom[idom[u]];}
    }
    for(int i=2; i<=n; i++)
    {
        if(idom[i]) {addedge(e0,en0,fe0,idom[i],i);}
    }
    dfs0(1);
    for(int i=1; i<=n; i++) printf("%d ",sz0[i]);
    return 0;
}
/*
7 7
1 5
1 4
1 2
3 7
4 3
4 6
6 7
*/

建议加强此题数据

讨论操作

回复

相关推荐

建议加强此题数据