Submission #470588

#TimeUsernameProblemLanguageResultExecution timeMemory
470588cp_is_hardJoker (BOI20_joker)C++14
14 / 100
2094 ms21828 KiB
#define wiwihorz #include <bits/stdc++.h> #pragma GCC optimize("Ofast") #pragma loop-opt(on) #define rep(i, a, b) for(int i = a; i <= b; i++) #define rrep(i, a, b) for(int i = b; i >= a; i--) #define all(x) x.begin(), x.end() #define ceil(a, b) using namespace std; #define INF 1000000000000000000 #define lld long double #define int long long int #define pii pair<int, int> #define random mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count()) #ifdef wiwihorz #define print(a...) kout("[" + string(#a) + "] = ", a) void vprint(auto L, auto R) { while(L < R) cerr << *L << " \n"[next(L) == R], ++L;} void kout() { cerr << endl; } template<class T1, class ... T2> void kout(T1 a, T2 ... e) { cerr << a << " ", kout(e...); } #else #define print(...) #define vprint(...) #endif namespace dsu { int n, cnt; vector<int> sz, par; stack<pair<int*, int>> st; void init_(int _n) { n = _n, cnt = 0; sz.assign(n + 1, 0); par.assign(n + 1, 0); rep(i, 1, n) sz[i] = 1, par[i] = i; } int find_par(int a) { while(a != par[a]) a = par[a]; return a; } bool same(int a, int b) { return find_par(a) == find_par(b); } void unite(int a, int b) { int aa = find_par(a); int bb = find_par(b); if(aa == bb) return; if(sz[aa] < sz[bb]) swap(aa, bb); cnt++; st.push({&par[bb], par[bb]}); st.push({&sz[aa], sz[aa]}); par[bb] = aa, sz[aa] += sz[bb]; } void undo() { if(!cnt) return; cnt--; pair<int*, int> p; p = st.top(); st.pop(), *p.first = p.second; p = st.top(); st.pop(), *p.first = p.second; } }; namespace solver { int n, m; vector<int> s; vector<pii> es; void init_(int _n, int _m) { n = _n, m = _m; s.assign(2 * m, 0); es.assign(2 * m, {0, 0}); dsu::init_(2 * n); } void solve(int L, int R, int l, int r) { int mid = (L + R) / 2, id = max(l, mid); if(L > R) return; int p1 = dsu::cnt; rep(i, mid, min(R, id - 1)) { dsu::unite(es[i].first, es[i].second + n); dsu::unite(es[i].first + n, es[i].second); } int p2 = dsu::cnt; while(id < r) { int x = es[id].first, y = es[id].second; if(dsu::same(x, y)) break; dsu::unite(x, y + n); dsu::unite(x + n, y); id ++; } s[mid] = id; while(dsu::cnt != p2) dsu::undo(); solve(L, mid - 1, l, id); while(dsu::cnt != p1) dsu::undo(); rep(i, R + 1, id - 1) { dsu::unite(es[i].first, es[i].second + n); dsu::unite(es[i].first + n, es[i].second); } solve(mid + 1, R, id, r); while(dsu::cnt != p1) dsu::undo(); return; } bool query(int L, int R) { L --, R --; int l = R + 1, r = m + L - 1; return s[l] <= r; } }; using namespace solver; signed main() { ios::sync_with_stdio(false), cin.tie(0); int n, m, q; cin >> n >> m >> q; init_(n, m); rep(i, 0, m - 1) { cin >> es[i].first; cin >> es[i].second; } rep(i, m, 2 * m - 1) es[i] = es[i - m]; solve(0, 2 * m - 1, 0, 2 * m); rep(i, 1, q) { int L, R; cin >> L >> R; cout << (query(L, R) ? "YES" : "NO") << "\n"; } return 0; }

Compilation message (stderr)

Joker.cpp:4: warning: ignoring '#pragma loop ' [-Wunknown-pragmas]
    4 | #pragma loop-opt(on)
      | 
Joker.cpp:21:13: warning: use of 'auto' in parameter declaration only available with '-fconcepts-ts'
   21 | void vprint(auto L, auto R) { while(L < R) cerr << *L << " \n"[next(L) == R], ++L;}
      |             ^~~~
Joker.cpp:21:21: warning: use of 'auto' in parameter declaration only available with '-fconcepts-ts'
   21 | void vprint(auto L, auto R) { while(L < R) cerr << *L << " \n"[next(L) == R], ++L;}
      |                     ^~~~
#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...