第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;
}