Submission #944388

#TimeUsernameProblemLanguageResultExecution timeMemory
944388sofiefuJoker (BOI20_joker)C++14
0 / 100
144 ms41656 KiB
#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 (stderr)

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 timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...