| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 944521 |
2024-03-12T21:07:40 Z |
sofiefu |
Joker (BOI20_joker) |
C++14 |
|
352 ms |
262144 KB |
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define vo vector
#define pb push_back
#define se second
#define fi first
#define sz(x) x.size()
typedef long long ll;
typedef vector<int> vi;
typedef pair<int, int> pii;
#define umap unordered_map
#define uset unordered_set
#define rep(i, a, b) for(ll i=(a); i<b; i++)
#define pr1(x) cerr << #x << '=' << x << ' ';
//for google contests
#define all(v) v.begin(), v.end()
#define repd(i, a, b) for(ll i=(b-1); i >= a; i--)
void _pr(signed x) {cerr << x;}
void _pr(long long x) {cerr << x;}
void _pr(unsigned long long x) {cerr << x;}
void _pr(double x) {cerr << x;}
void _pr(char x) {cerr << '\'' << x << '\'';}
void _pr(const char* x) {cerr << x;}
void _pr(bool x) {cerr << (x ? "true" : "false");}
template<typename T, typename V> void _pr(const pair<T, V> &x);
template<typename T, typename V> void _pr(const pair<T, V> &x) {cerr << "\e[95m" << "[ "; _pr(x.first); cerr << ", "; _pr(x.second); cerr << "\e[95m" << ']';}
template<typename T> void _pr(const T &x) {int F=0; cerr << '{'; for(auto &i: x) cerr << (F++ ? ", " : ""), _pr(i); cerr << "\e[91m" << '}';}
template <typename T, typename... V> void _pr(T t, V... v) {_pr(t); if(sizeof...(v)) cerr << ", "; _pr(v...);}
#define pr(x...) cerr << "\e[91m" << __func__ << ':' << __LINE__ << " [" << #x << "] = ["; _pr(x); cerr << "\e[91m" << ']' << "\033[0m" << endl;
//go for outline with ;, then details
ll const inf = LLONG_MAX, mxn = 2e5+4;
int n, m, q, B = sqrt(2e5), ans[mxn];
vo<vi> adj(mxn);
vo<pii> edges;
struct DSU{
vi par, rnk, color;
vo<array<int, 5>> bipartite = {{1, 0, 0, 0, 0}, {1, 0, 0, 0, 0}};
vo<pii> st;
DSU(int n): par(n), rnk(n), color(n, 0){
rep(i, 0, n) par[i] = i;
}
int findpar(int v){
if(v==par[v]) return v;
return findpar(par[v]);
}
void unite(int a, int b){
if(!bipartite.back()[0]){
bipartite.pb({0, a, b, color[a], color[b]});
}
else{
if(color[a] == color[b] && color[a] != 0){
bipartite.pb({0, a, b, color[a], color[b]});
}
else{
bipartite.pb({1, a, b, color[a], color[b]});
if(color[a]) color[b] = color[a]*-1;
else if(color[b]) color[a] = color[b]*-1;
else {
color[a] = 1, color[b] = -1;
}
}
}
// pr("merge", a, b, color)
a = findpar(a), b = findpar(b);
if(rnk[b] > rnk[a]) swap(a, b);
st.pb({a, rnk[a]});
st.pb({b, rnk[b]});
par[b] = a;
if(rnk[a] == rnk[b]) rnk[a]++;
}
void rollback(){
rep(i, 0, 2){
pii v = st.back();
par[v.fi] = v.fi; rnk[v.fi] = v.se;
st.pop_back();
}
auto [prev, a, b, c1, c2] = bipartite.back();
color[a] = c1, color[b] = c2;
bipartite.pop_back();
// pr("rollback", color)
}
};
signed main(){
cin.tie(0)->sync_with_stdio(0);
cin>>n>>m>>q;
vo<set<array<int, 3>>> block(m/B+1); //r l
rep(i, 0, m){
int a, b; cin>>a>>b; a--, --b;
adj[a].pb(b), adj[b].pb(a);
edges.pb({a, b});
}
rep(i, 0, q){
int l, r; cin>>l>>r; l--, --r;
block[l/B].insert({r, l, i});
}
DSU g(n);
int p1 = 0;
// pr(block)
rep(i, 0, sz(block)){
if(!sz(block[i])) continue;
if(i*B > m) break;
int nexp1 = min(m, i*B), p2 = m;
// pr(p1, nexp1)
rep(u, p1, nexp1) g.unite(edges[u].fi, edges[u].se);
p1 = nexp1;
for(auto [r, l, queryind]: block[i]){
// pr(l, r, queryind)
if(r < p2){
repd(u, r+1, m){
// pr(r+1, m, edges[u])
g.unite(edges[u].fi, edges[u].se);
p2 = r+1;
}
}
else{
rep(u, p2, r+1){
g.rollback();
p2 = r+1; //weird
}
}
rep(u, p1, l){
// pr(u, edges[u])
g.unite(edges[u].fi, edges[u].se);
}
//check bipartit
// pr(g.bipartite.back())
// pr(g.color)
ans[queryind] = !g.bipartite.back()[0];
rep(u, p1, l){
g.rollback();
}
}
rep(u, p2, m) g.rollback(); //from the right
}
vo<string> ret = {"NO", "YES"};
rep(i, 0, q) cout << ret[ans[i]] << "\n";
}
/*
4 4 3
1 2
2 3
3 1
1 4
1 2
4 4
2 3
6 8 1
1 3
1 5
1 6
2 5
2 6
3 4
3 5
5 6
4 8
*/
Compilation message
Joker.cpp: In member function 'void DSU::rollback()':
Joker.cpp:87:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
87 | auto [prev, a, b, c1, c2] = bipartite.back();
| ^
Joker.cpp: In function 'int main()':
Joker.cpp:15:37: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<std::set<std::array<long long int, 3> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
15 | #define rep(i, a, b) for(ll i=(a); i<b; i++)
| ^
Joker.cpp:113:5: note: in expansion of macro 'rep'
113 | rep(i, 0, sz(block)){
| ^~~
Joker.cpp:121:18: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
121 | for(auto [r, l, queryind]: block[i]){
| ^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
4952 KB |
Output is correct |
| 2 |
Correct |
3 ms |
4952 KB |
Output is correct |
| 3 |
Correct |
2 ms |
4956 KB |
Output is correct |
| 4 |
Correct |
2 ms |
4956 KB |
Output is correct |
| 5 |
Incorrect |
2 ms |
4956 KB |
Output isn't correct |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
4952 KB |
Output is correct |
| 2 |
Correct |
3 ms |
4952 KB |
Output is correct |
| 3 |
Correct |
2 ms |
4956 KB |
Output is correct |
| 4 |
Correct |
2 ms |
4956 KB |
Output is correct |
| 5 |
Incorrect |
2 ms |
4956 KB |
Output isn't correct |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
4952 KB |
Output is correct |
| 2 |
Correct |
3 ms |
4952 KB |
Output is correct |
| 3 |
Runtime error |
352 ms |
262144 KB |
Execution killed with signal 9 |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
4952 KB |
Output is correct |
| 2 |
Correct |
3 ms |
4952 KB |
Output is correct |
| 3 |
Correct |
2 ms |
4956 KB |
Output is correct |
| 4 |
Correct |
2 ms |
4956 KB |
Output is correct |
| 5 |
Incorrect |
2 ms |
4956 KB |
Output isn't correct |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
4952 KB |
Output is correct |
| 2 |
Correct |
3 ms |
4952 KB |
Output is correct |
| 3 |
Correct |
2 ms |
4956 KB |
Output is correct |
| 4 |
Correct |
2 ms |
4956 KB |
Output is correct |
| 5 |
Incorrect |
2 ms |
4956 KB |
Output isn't correct |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
4952 KB |
Output is correct |
| 2 |
Correct |
3 ms |
4952 KB |
Output is correct |
| 3 |
Correct |
2 ms |
4956 KB |
Output is correct |
| 4 |
Correct |
2 ms |
4956 KB |
Output is correct |
| 5 |
Incorrect |
2 ms |
4956 KB |
Output isn't correct |
| 6 |
Halted |
0 ms |
0 KB |
- |
