This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
#define ll long long
#define ld long double
#define ull unsigned long long
#define pb push_back
#define pll pair<ll, ll>
#define pii pair<int, int>
#define fi first
#define se second
using namespace std;
const int N = 3e5+5;
const int M = 21;
const ll inf = 4e18;
const ll mod = 998244353;
int n, t, m, k, ans, tong, a[N], lab[N], d[N], b[N], c[N];
pii dp[N];
vector<int> vi;
string s;
struct node
{
int x, vx, y, vy;
node(){}
node(int _x, int _vx, int _y, int _vy)
{
x = _x;
vx = _vx;
y = _y;
vy = _vy;
}
};
vector<node> q;
pii findp(int u)
{
int bi = 0;
while(lab[u] > 0)
{
bi ^= c[u];
u = lab[u];
}
return {u, bi};
}
bool hop(int u, int v)
{
pii x = findp(u), y = findp(v);
if(x.fi == y.fi)
{
if(x.se == y.se)return false;
return true;
}
q.pb(node(x.fi, lab[x.fi], y.fi, lab[y.fi]));
if(lab[x.fi] > lab[y.fi])swap(x, y);
lab[x.fi] += lab[y.fi];
lab[y.fi] = x.fi;
c[y.fi] = x.se^y.se^1;
return true;
}
void rollback(int sz)
{
while((int)q.size() > sz)
{
node u = q.back();
q.pop_back();
lab[u.x] = u.vx;
lab[u.y] = u.vy;
}
}
void cal(int l, int r, int opl, int opr)
{
if(l > r)return;
int mid = (l+r)>>1;
int sz = q.size();
bool ok = true;
for(int i = l; i <= mid; i ++)
{
if(!hop(a[i], b[i]))
{
ok = false;
break;
}
}
if(ok)
{
int sz1 = q.size();
d[mid] = max(opr, mid+1)-1;
for(int i = min(opr, m); i >= max(opl, mid+1); i --)
{
if(!hop(a[i], b[i]))
{
break;
d[mid] = i;
}
}
rollback(sz1);
cal(mid+1, r, d[mid], opr);
}
//cout << mid <<" "<<d[mid]<<" "<<ok << '\n';
rollback(sz);
for(int i = d[mid]+1; i <= opr; i ++)hop(a[i], b[i]);
cal(l, mid-1, opl, d[mid]);
rollback(sz);
}
void sol()
{
cin >> n >> m >> t;
fill_n(lab, n+1, -1);
for(int i = 1; i <= m; i ++)
{
cin >> a[i] >> b[i];
d[i] = m+1;
}
cal(1, m, 1, m);
while(t -- > 0)
{
int l, r;
cin >> l >> r;
if(d[l] >= r)cout << "YES" << '\n';
else cout << "NO" << '\n';
}
}
int main()
{
cin.tie(0);
cout.tie(0);
ios_base::sync_with_stdio(0);
#define task "test"
if(fopen(task".inp", "r"))
{
freopen(task".inp", "r", stdin);
freopen(task".out", "w", stdout);
}
int ntest = 1;
//cin >> ntest;
while(ntest -- > 0)
sol();
}
Compilation message (stderr)
Joker.cpp: In function 'int main()':
Joker.cpp:130:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
130 | freopen(task".inp", "r", stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
Joker.cpp:131:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
131 | freopen(task".out", "w", stdout);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |