Educational Codeforce #72 F. Forced Online Queries Problem
https://codeforces.com/contest/1217/problem/F
It didn't take long to come up with a solution, but I couldn't remove bugs during a contest.
I always make mistakes due to index variables name and loop range. To avoid them, I wrote a code which gives special type to native int. There are a lot of kinds of integers. For example, the one means vertex number and the other means edge number. I want to discriminate them.
The code is like this.
VERTEX N; EDGE M; vec<VERTEX, EDGE> a(N, EDGE()); vec<EDGE, QUERY> b(M, QUERY()); for (VERTEX i(0); i < a.size(); i++) { cout << b[a[i]] << endl; } // for (VERTEX i(0); i < a.size(); i++) { <--- ERROR // cout << b[i] << endl; //} // ERROR: b[_] takes EDGE but i is VERTEX // // for (VERTEX i(0); i < b.size(); i++) { <-- ERROR // cout << b[a[i]] << endl; //} // ERROR: i is VERTEX but b.size() is EDGE // // for (EDGE i(0); i < b.size(); i++) { // cout << a[b[i]] << endl; <-- ERROR //} // ERROR: a[_] takes VERTEX, but b[i] is QUERY
#include <bits/stdc++.h> #define rep(i, n) for (int i = 0; i < (n); i++) #define repr(i, n) for (int i = (n) - 1; i >= 0; i--) #define range(a) a.begin(), a.end() using namespace std; using ll = long long; #define INDEX_TYPE(T)\ class T {\ int x;\ public:\ T() {}\ constexpr explicit T(int x_) : x(x_) {}\ explicit operator int() { return x; }\ T operator++(int) { return T(x++); }\ T operator--(int) { return T(x--); }\ friend T operator+(T a, T b) { return T(a.x + b.x); }\ T &operator+=(T b) { x += b.x; return *this; }\ friend bool operator<(T a, T b) { return a.x < b.x; }\ friend bool operator<=(T a, T b) { return a.x <= b.x; }\ friend bool operator>(T a, T b) { return a.x > b.x; }\ friend bool operator>=(T a, T b) { return a.x >= b.x; }\ friend bool operator==(T a, T b) { return a.x == b.x; }\ friend bool operator!=(T a, T b) { return a.x != b.x; }\ friend istream &operator>>(istream &i, T &a) { return i >> a.x; }\ }; template<class A, class B> struct vec { vector<B> dat; vec(A n, B e) : dat((int)n, e) {} A size() { return A(dat.size()); } B &operator[](A a) { assert(0 <= (int)a && (int)a < dat.size()); return dat[(int)a]; } }; template<class A, class B> struct dynvec { vector<B> dat; dynvec() {} void push(B b) { dat.push_back(b); } B pop() { B res = dat.back(); dat.pop_back(); return res; } void clear() { dat.clear(); } A size() { return A(dat.size()); } B &operator[](A a) { assert(0 <= (int)a && (int)a < dat.size()); return dat[(int)a]; } void uniq() { sort(dat.begin(), dat.end()); dat.erase(unique(dat.begin(), dat.end()), dat.end()); } A index(B b) { return A(lower_bound(dat.begin(), dat.end(), b) - dat.begin()); } }; INDEX_TYPE(VERTEX); INDEX_TYPE(EDGE); INDEX_TYPE(QUERY); using BOOL = char; constexpr QUERY S = QUERY(1000); struct union_find { vec<VERTEX, int> dat; dynvec<int, pair<VERTEX, int>> history; union_find(VERTEX n) : dat(n, -1) {} VERTEX find(VERTEX x) { while (dat[x] >= 0) x = VERTEX(dat[x]); return x; } void unite(pair<VERTEX, VERTEX> e) { VERTEX x = e.first; VERTEX y = e.second; x = find(x); y = find(y); if (x == y) return; if (-dat[x] < -dat[y]) swap(x, y); history.push(make_pair(x, dat[x])); history.push(make_pair(y, dat[y])); dat[x] += dat[y]; dat[y] = (int)x; } void init() { clear_history(); for (VERTEX i(0); i < dat.size(); i++) { dat[i] = -1; } } void clear_history() { history.clear(); } void rollback() { while (history.size() > 0) { auto p = history.pop(); dat[ p.first ] = p.second; } } }; pair<VERTEX, VERTEX> mm(VERTEX x, VERTEX y) { return make_pair(min(x, y), max(x, y)); } #define exrep(ty, i, n) for (ty i = ty(0); i < n; i++) int main() { cin.tie(nullptr); ios::sync_with_stdio(false); VERTEX N; QUERY M; cin >> N >> M; dynvec<EDGE, pair<VERTEX, VERTEX>> es; vec<QUERY, int> TYPE(M, 0); vec<QUERY, VERTEX> X(M, VERTEX(0)), Y(M, VERTEX(0)); auto succ = [N](VERTEX u) -> VERTEX { u++; return u == N ? VERTEX(0) : u; }; exrep(QUERY, i, M) { cin >> TYPE[i] >> X[i] >> Y[i]; X[i]--; Y[i]--; if (TYPE[i] == 1) { es.push(mm(X[i], Y[i])); es.push(mm(succ(X[i]), succ(Y[i]))); } } es.uniq(); vec<QUERY, EDGE> E0(M, EDGE(0)); vec<QUERY, EDGE> E1(M, EDGE(0)); vec<QUERY, EDGE> E(M, EDGE(0)); exrep(QUERY, i, M) if (TYPE[i] == 1) { E0[i] = es.index(mm(X[i], Y[i])); E1[i] = es.index(mm(succ(X[i]), succ(Y[i]))); } vec<EDGE, BOOL> used(es.size(), false); vec<EDGE, BOOL> may(es.size(), false); dynvec<EDGE, EDGE> what; int last = 0; union_find uf(N); for (QUERY l = QUERY(0); l < QUERY(M); l += S) { QUERY r = min(M, l + S); uf.init(); what.clear(); for (EDGE i = EDGE(0); i < EDGE(es.size()); i++) { used[i] = false; may[i] = false; } for (QUERY j = l; j < r; j++) if (TYPE[j] == 1) { may[E0[j]] = true; may[E1[j]] = true; } for (EDGE j = EDGE(0); j < es.size(); j++) { if (may[j]) { what.push(j); } } for (QUERY j = QUERY(0); j < l; j++) if (TYPE[j] == 1) { used[E[j]] ^= 1; } for (EDGE j = EDGE(0); j < es.size(); j++) { if (!may[j] && used[j]) { uf.unite(es[j]); } } uf.clear_history(); for (QUERY j = l; j < r; j++) { if (TYPE[j] == 1) { E[j] = last == 0 ? E0[j] : E1[j]; } else { for (QUERY k = l; k < j; k++) if (TYPE[k] == 1) used[E[k]] ^= 1; for (EDGE k = EDGE(0); k < what.size(); k++) if (used[what[k]]) { uf.unite(es[what[k]]); } VERTEX x = last == 0 ? X[j] : succ(X[j]); VERTEX y = last == 0 ? Y[j] : succ(Y[j]); last = uf.find(x) == uf.find(y); cout << last; uf.rollback(); for (QUERY k = l; k < j; k++) if (TYPE[k] == 1) used[E[k]] ^= 1; } } } cout << endl; }