| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 258618 |
2020-08-06T08:57:33 Z |
Diuven |
Joker (BOI20_joker) |
C++14 |
|
2000 ms |
9204 KB |
#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> pii;
const int MAX = 200010;
struct edge_t { int u, v; };
struct stat_t { int x, p, c, s, b; };
inline int _min(int a, int b){ return a<b ? a : b; }
inline int _max(int a, int b){ return a>b ? a : b; }
class uf_t {
int n, U[MAX], C[MAX], S[MAX];
vector<stat_t> hist;
bool bip;
int find(int x){
return x == U[x] ? x : find(U[x]);
}
stat_t unite(int x, int y){
stat_t bef = {0, 0, 0, 0, bip};
int u = find(x), a = C[x];
int v = find(y), b = C[y];
if(u==v){
if(a==b) bip = false;
return bef;
}
//if(sz[u]<sz[v]) swap(u,v);
bef = {v, U[v], C[v], 0, bip};
U[v]=u; C[v]=a^b^1;
return bef;
}
public:
uf_t(int sz){
n = sz; bip = true;
iota(U, U+n+1, 0);
fill(C, C+n+1, 0);
fill(S, S+n+1, 1);
}
void add_edge(edge_t e){
stat_t now = unite(e.v, e.u);
hist.push_back(now);
}
void pop_edge(){
stat_t now = hist.back(); hist.pop_back();
bip = now.b;
int v = now.x;
if(v==0) return;
U[v] = now.p; C[v] = now.c;
}
bool is_bip(){
return bip;
}
};
int n, m, q;
edge_t E[MAX];
int pos[MAX];
// pos[l] : using ([1,l] + [pos[l], m]) is bipartite
void solve(int s, int e, int l, int r, uf_t &UF){
// UF set as [1, s) + (r, m]
if(e>s) return;
int mid = (s+e)/2, &p = pos[mid];
for(int i=_max(1, s); i<=mid; i++)
UF.add_edge(E[i]);
// [1, mid] + (r, m]
int bgn = _min(r, m), fin = _max(l, mid+1);
for(int i=bgn; i>=fin; i--){
UF.add_edge(E[i]);
if(UF.is_bip()) p=i;
}
int sto = _min(bgn, p);
// [1, mid] + [fin, m]
for(int i=fin; i<=sto; i++)
UF.pop_edge();
// [1, mid] + (sto, m]
solve(s, mid-1, l, p, UF);
// set UF
solve(mid+1, e, p, r, UF);
}
int main(){
ios::sync_with_stdio(0); cin.tie(0);
cin>>n>>m>>q;
for(int i=1; i<=m; i++){
int u, v; cin>>u>>v;
E[i] = {u, v};
}
fill(pos, pos+m+1, m+2);
static uf_t UF(n);
// solve(0, m, 1, m+1, UF);
for(int i=1; i<=q; i++){
int l, r; cin>>l>>r;
for(int j=1; j<l; j++)
UF.add_edge(E[j]);
for(int j=m; j>r; j--)
UF.add_edge(E[j]);
cout<<(UF.is_bip() ? "NO" : "YES")<<'\n';
for(int j=1; j<l; j++)
UF.pop_edge();
for(int j=m; j>r; j--)
UF.pop_edge();
// cout<<(pos[l-1] <= r+1 ? "NO" : "YES")<<'\n';
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
512 KB |
Output is correct |
| 2 |
Correct |
0 ms |
384 KB |
Output is correct |
| 3 |
Correct |
0 ms |
384 KB |
Output is correct |
| 4 |
Correct |
0 ms |
384 KB |
Output is correct |
| 5 |
Correct |
0 ms |
384 KB |
Output is correct |
| 6 |
Incorrect |
0 ms |
384 KB |
Output isn't correct |
| 7 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
512 KB |
Output is correct |
| 2 |
Correct |
0 ms |
384 KB |
Output is correct |
| 3 |
Correct |
0 ms |
384 KB |
Output is correct |
| 4 |
Correct |
0 ms |
384 KB |
Output is correct |
| 5 |
Correct |
0 ms |
384 KB |
Output is correct |
| 6 |
Incorrect |
0 ms |
384 KB |
Output isn't correct |
| 7 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
512 KB |
Output is correct |
| 2 |
Correct |
0 ms |
384 KB |
Output is correct |
| 3 |
Execution timed out |
2078 ms |
9204 KB |
Time limit exceeded |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
512 KB |
Output is correct |
| 2 |
Correct |
0 ms |
384 KB |
Output is correct |
| 3 |
Correct |
0 ms |
384 KB |
Output is correct |
| 4 |
Correct |
0 ms |
384 KB |
Output is correct |
| 5 |
Correct |
0 ms |
384 KB |
Output is correct |
| 6 |
Incorrect |
0 ms |
384 KB |
Output isn't correct |
| 7 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
512 KB |
Output is correct |
| 2 |
Correct |
0 ms |
384 KB |
Output is correct |
| 3 |
Correct |
0 ms |
384 KB |
Output is correct |
| 4 |
Correct |
0 ms |
384 KB |
Output is correct |
| 5 |
Correct |
0 ms |
384 KB |
Output is correct |
| 6 |
Incorrect |
0 ms |
384 KB |
Output isn't correct |
| 7 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
512 KB |
Output is correct |
| 2 |
Correct |
0 ms |
384 KB |
Output is correct |
| 3 |
Correct |
0 ms |
384 KB |
Output is correct |
| 4 |
Correct |
0 ms |
384 KB |
Output is correct |
| 5 |
Correct |
0 ms |
384 KB |
Output is correct |
| 6 |
Incorrect |
0 ms |
384 KB |
Output isn't correct |
| 7 |
Halted |
0 ms |
0 KB |
- |
