RE求调70pts
  • 板块P2416 泡芙
  • 楼主Elysialr
  • 当前回复0
  • 已保存回复0
  • 发布时间2024/11/20 16:47
  • 上次更新2024/11/20 16:52:25
查看原帖
RE求调70pts
1263684
Elysialr楼主2024/11/20 16:47
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define SIZE 500001

struct road{
    ll ver,Next;
    bool bridge;
    bool puff;
};
struct node{
    ll head;
    ll dfn,low;
    ll g;
};

ll n,m,q,logn;
ll tot=1,num;
node f[SIZE];
road r[SIZE];
vector<vector<ll>> dcc;
bool pf[SIZE];
ll puff[SIZE];
ll fa[SIZE][20];
ll d[SIZE];

void add(ll x,ll y,bool z){
    tot++;
    r[tot].ver=y;
    r[tot].puff=z;
    r[tot].Next=f[x].head;
    f[x].head=tot;
}
void tarjan(ll x,ll edge){
    f[x].dfn=f[x].low=++num;
    for(ll i=f[x].head;i!=0;i=r[i].Next){
        ll y=r[i].ver;

        if(f[y].dfn==0){
            tarjan(y,i);
            f[x].low=min(f[x].low,f[y].low);

            if(f[y].low>f[x].dfn)
            r[i].bridge=r[i^1].bridge=true;
        }
        else if(i!=(edge^1)) f[x].low=min(f[x].low,f[y].dfn);
    }
}
void finds(ll x){
    dcc.back().push_back(x);
    for(ll i=f[x].head;i!=0;i=r[i].Next){
        ll y=r[i].ver;
        if(r[i].bridge) continue;
        if(r[i].puff){puff[f[x].g]++;pf[f[x].g]=true;}
        if(f[y].g!=0) continue;
        f[y].g=f[x].g;
        finds(y);
    }
}
void dfs(ll x){
    for(ll i=0;i<dcc[x].size();i++)
    for(ll j=f[dcc[x][i]].head;j!=0;j=r[j].Next)
    if(r[j].bridge){
        ll y=f[r[j].ver].g;
        if(y==fa[x][0]) continue;
        if(r[j].puff) puff[y]++;
        fa[y][0]=x;

        d[y]=d[x]+1;
        puff[y]+=puff[x];
        for(ll j=1;j<=logn;j++)
        fa[y][j]=fa[fa[y][j-1]][j-1];
        dfs(y);
    }
}
ll lca(ll x,ll y){
    if(d[x]<d[y]) return lca(y,x);

    for(ll i=logn;i>=0;i--)
    if(d[fa[x][i]]>=d[y])
    x=fa[x][i];

    if(x==y) return x;

    for(ll i=logn;i>=0;i--)
    if(fa[x][i]!=fa[y][i]){
        x=fa[x][i];
        y=fa[y][i];
    }
    return fa[x][0];
}
bool judge(ll x,ll y){
    if(pf[x]||pf[y]) return true;
    return puff[x]+puff[y]-2*puff[lca(x,y)];
}

void init(){
    cin>>n>>m;
    for(ll i=1;i<=m;i++){
        ll x,y,z;
        cin>>x>>y>>z;
        add(x,y,z);
        add(y,x,z);
    }
}
void prepare(){
    for(ll x=1;x<=n;x++)
    if(f[x].dfn==0)
    tarjan(x,0);

    dcc.push_back(vector<ll>());
    for(ll i=1;i<=n;i++)
    if(f[i].g==0){
        f[i].g=dcc.size();
        dcc.push_back(vector<ll>());
        finds(i);
    }
    logn=(ll)(log2(dcc.size())+1);
    d[1]=1;
    dfs(1);
}
void solve(){
    cin>>q;
    while(q--){
        ll x,y;
        cin>>x>>y;
        x=f[x].g;
        y=f[y].g;
        if(judge(x,y)) cout<<"YES\n";
        else cout<<"NO\n";
    }
}
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);

    init();
    prepare();
    solve();
    return 0;
}
2024/11/20 16:47
加载中...