| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 944388 |
2024-03-12T16:27:24 Z |
sofiefu |
Joker (BOI20_joker) |
C++14 |
|
144 ms |
41656 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, bipartite = {1, 1};
vo<pii> st;
DSU(int n): par(n), rnk(n), color(n){
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()){
bipartite.pb(0);
}
else{
if(color[a] == color[b] && color[a] != 0){
bipartite.pb(0);
}
else{
if(color[a]) color[b] = color[a]*=-1;
else if(color[b]) color[a] = color[b]*=-1;
else {
color[a] = 1, color[b] = -1;
}
bipartite.pb(1);
}
}
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();
}
bipartite.pop_back();
}
};
signed main(){
cin.tie(0)->sync_with_stdio(0);
cin>>n>>m>>q;
vo<set<array<int, 3>>> block(B); //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 prev = 0, p1 = 0, p2 = m;
rep(i, 0, sz(block)){
if(!sz(block[i])) continue;
int nexp1 = min(m, i*B);
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)c
if(r < p2){
repd(u, r+1, m){
g.unite(edges[u].fi, edges[u].se);
p2 = r+1;
}
}
else{
rep(u, p2, r){
// pr(p2, r)
g.rollback();
p2 = r;
}
}
rep(u, nexp1, l){
g.unite(edges[u].fi, edges[u].se);
}
//check bipartit
if(g.bipartite.back()) ans[queryind] = 0;
else ans[queryind] = 1;
rep(u, nexp1, l){
// pr(g.st)
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 5
1 2
2 3
3 1
1 4
4 4
1 1
1 2
2 3
4 4
*/
Compilation message
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:107:5: note: in expansion of macro 'rep'
107 | rep(i, 0, sz(block)){
| ^~~
Joker.cpp:113:18: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
113 | for(auto [r, l, queryind]: block[i]){
| ^
Joker.cpp:106:9: warning: unused variable 'prev' [-Wunused-variable]
106 | int prev = 0, p1 = 0, p2 = m;
| ^~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
4952 KB |
Output is correct |
| 2 |
Correct |
1 ms |
4956 KB |
Output is correct |
| 3 |
Correct |
2 ms |
4956 KB |
Output is correct |
| 4 |
Incorrect |
2 ms |
4956 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
4952 KB |
Output is correct |
| 2 |
Correct |
1 ms |
4956 KB |
Output is correct |
| 3 |
Correct |
2 ms |
4956 KB |
Output is correct |
| 4 |
Incorrect |
2 ms |
4956 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
4952 KB |
Output is correct |
| 2 |
Correct |
1 ms |
4956 KB |
Output is correct |
| 3 |
Incorrect |
144 ms |
41656 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
4952 KB |
Output is correct |
| 2 |
Correct |
1 ms |
4956 KB |
Output is correct |
| 3 |
Correct |
2 ms |
4956 KB |
Output is correct |
| 4 |
Incorrect |
2 ms |
4956 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
4952 KB |
Output is correct |
| 2 |
Correct |
1 ms |
4956 KB |
Output is correct |
| 3 |
Correct |
2 ms |
4956 KB |
Output is correct |
| 4 |
Incorrect |
2 ms |
4956 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
4952 KB |
Output is correct |
| 2 |
Correct |
1 ms |
4956 KB |
Output is correct |
| 3 |
Correct |
2 ms |
4956 KB |
Output is correct |
| 4 |
Incorrect |
2 ms |
4956 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
