90分求助(WA on 8, 和讨论区另一个90分不一样)
查看原帖
90分求助(WA on 8, 和讨论区另一个90分不一样)
762588
Edgebright楼主2023/7/24 11:25

第8个点:Wrong Answer.wrong answer On line 77363 column 1, read N, expected Y.

#include<bits/stdc++.h>
using namespace std;
const int N = 100005;
int n, m, k;
struct edge
{
    int u, v;
};
vector<edge> e[N << 2];
struct opt
{
    int x, y, add;
}s[N << 1];
int top;
struct unionfind
{
    int fa[N << 1];
    int hei[N << 1];
    inline void init(int Mx)
    {
        for(int i = 1; i <= Mx; ++i)
        {
            fa[i] = i;
            hei[i] = 1;
        }return;
    }
    inline int find(int x)
    {
        while(fa[x] != x)
        {
            x = fa[x];
        }
        return x;
    }
    inline void merge(int x, int y)
    {
        x = find(x); y = find(y);
        if(hei[x] > hei[y]) swap(x, y);
        fa[x] = y;
        s[++top] = {x, y, hei[x] == hei[y]};
        if(hei[x] == hei[y]) ++hei[y];
        return;
    }
};
unionfind uf;

void add(int p, int L, int R, edge ed, int l, int r)
{
    if(l <= L && R <= r)
    {
        e[p].push_back(ed); return;
    }
    int md = (L + R) >> 1;
    if(l <= md)
    {
        add(p<<1, L, md, ed, l, r);
    }
    if(md < r)
    {
        add(p<<1|1, md + 1, R, ed, l, r);
    }
    return;
}
void solve(int p, int L, int R)
{
    int bipart = 1, lasttop = top;
    for(edge ed : e[p])
    {
        int u = ed.u, v = ed.v;
        if(uf.find(u) == uf.find(v))
        {
            bipart = 0;
            for(int i = L; i <= R; ++i) puts("No");
            return;
        }
        uf.merge(u, v + n); uf.merge(v, u + n);
    }
    if(L == R)
    {
        puts("Yes"); return;
    }
    int md = (L + R) >> 1;
    solve(p<<1, L, md); solve(p<<1|1, md + 1, R);
    while(top > lasttop)
    {
        opt del = s[top];
        uf.fa[del.x] = del.x;
        uf.hei[del.y] -= del.add;//
        --top;
    }
    return;
}
template<class io>
inline void re(io &x)
{
    char c=getchar();x=0;
    while(c<48 || c>57)c=getchar();
    while(c>47 && c<58)x=(x<<3)+(x<<1)+(c&15),c=getchar();
    return;
}
signed main()
{
    freopen("segdiv.in", "r", stdin);
    re(n); re(m); re(k);
    uf.init(n * 2);
    for(int i = 1; i <= m; ++i)
    {
        int x, y, l, r;
        re(x); re(y); re(l); re(r);
        ++l;
        add(1, 1, k, {x, y}, l, r);
    }
    solve(1, 1, k);
    return 0;
}
2023/7/24 11:25
加载中...