Submission #389069

#TimeUsernameProblemLanguageResultExecution timeMemory
389069arujbansalJoker (BOI20_joker)C++17
0 / 100
242 ms10620 KiB
#include <iostream> #include <algorithm> #include <vector> #include <map> #include <set> #include <array> #include <stack> #include <queue> #include <random> #include <numeric> #include <functional> #include <chrono> #include <utility> #include <iomanip> #include <assert.h> using namespace std; void dbg_out() { cerr << endl; } template<typename Head, typename... Tail> void dbg_out(Head H, Tail... T) { cerr << ' ' << H; dbg_out(T...); } #define dbg(...) cerr << "(" << #__VA_ARGS__ << "):", dbg_out(__VA_ARGS__) #define rng_init mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()) #define rng_seed(x) mt19937 rng(x) #define all(x) (x).begin(), (x).end() #define sz(x) (int) (x).size() // #define int long long const int MXN = 2e5 + 5, INF = 1e9 + 5; int N, M, Q; pair<int, int> edges[MXN]; int info[MXN], parity[MXN]; int is_bipartite; stack<array<int, 3>> changes; // {node, size of component, did this make the graph non bipartite} int valid[MXN]; int find_par(int x) { if (info[x] < 0) return x; int p = find_par(info[x]); parity[x] ^= parity[info[x]]; return p; } void unite(int x, int y) { int px = find_par(x), py = find_par(y); if (px == py) { if (parity[x] == parity[y]) { changes.emplace(array<int, 3>{py, -info[py], is_bipartite}); is_bipartite = 0; } return; } if (info[px] > info[py]) { swap(px, py); swap(x, y); } changes.emplace(array<int, 3>{py, -info[py], 0}); parity[py] = parity[x] ^ parity[y] ^ 1; info[px] += info[py]; info[py] = px; } void rollback() { assert(changes.empty() == false); auto [y, comp_sz, non_bipartite] = changes.top(); int x = info[y]; if (x == y) return; info[x] += comp_sz; info[y] = -comp_sz; if (non_bipartite) is_bipartite = 1; changes.pop(); } void dnc(int l, int r, int optl, int optr) { if (l > r) return; // dbg(l, r); int mid = (l + r) / 2, ufds_r = optr; while (ufds_r > mid + 1 && ufds_r > optl && is_bipartite) { ufds_r--; unite(edges[ufds_r].first, edges[ufds_r].second); } valid[mid] = (is_bipartite ? 0 : ufds_r); int midl = (l + mid - 1) / 2, midr = (mid + 1 + r) / 2, best = ufds_r; while (ufds_r < optr) { rollback(); ufds_r++; } for (int i = mid; i < midr; i++) unite(edges[i].first, edges[i].second); dnc(mid + 1, r, best, optr); for (int i = mid; i < midr; i++) rollback(); for (int i = mid - 1; i >= midl; i--) rollback(); for (int i = ufds_r - 1; i >= best; i--) unite(edges[i].first, edges[i].second); dnc(l, mid - 1, optl, ufds_r); for (int i = midl; i < mid; i++) unite(edges[i].first, edges[i].second); } void solve() { cin >> N >> M >> Q; for (int i = 0; i < M; i++) { cin >> edges[i].first >> edges[i].second; edges[i].first--, edges[i].second--; } is_bipartite = 1; for (int i = 0; i < MXN; i++) info[i] = -1, parity[i] = 0; for (int i = 0; i < M / 2; i++) unite(edges[i].first, edges[i].second); dnc(0, M - 1, 0, M); while (Q--) { int l, r; cin >> l >> r; l--, r--; cout << (valid[l] > r ? "YES" : "NO") << "\n"; } } signed main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); int TC = 1; // cin >> TC; while (TC--) solve(); }
#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...