Submission #649840

#TimeUsernameProblemLanguageResultExecution timeMemory
649840welleythJoker (BOI20_joker)C++17
39 / 100
2101 ms35636 KiB
#include <bits/stdc++.h> #include <ext/pb_ds/assoc_container.hpp> #include <ext/pb_ds/tree_policy.hpp> using namespace std; using namespace __gnu_pbds; //#define int long long #define pb push_back #define mp make_pair #pragma GCC optimize("Ofast") #pragma GCC optimize("unroll-loops") #pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt") constexpr int N = (int)2e5 + 111; constexpr int md = (int)2e5 + 111; mt19937 rnd(time(nullptr)); vector<int> g[N]; bool used[2][N]; bool c[2][N]; bool dfs(int v,int r,int pr = -1){ used[r][v] = true; c[r][v] = true; for(auto& to : g[v]){ if(pr == to) continue; if(used[r^1][to]){ if(c[r][v]&c[r][to]) return true; continue; } c[r^1][to] = true; if(dfs(to,r^1,v)) return true; } return false; } int n,m,q; vector<pair<int,int>> edges; bool can(int l,int r){ for(int j = 0; j <= n; j++){ used[0][j] = false; used[1][j] = false; c[0][j] = c[1][j] = 0; g[j].clear(); } bool have = false; for(int j = 0; j < l-1; j++){ auto&[a,b] = edges[j]; g[a].pb(b); g[b].pb(a); } for(int j = r; j < m; j++){ auto&[a,b] = edges[j]; g[a].pb(b); g[b].pb(a); } for(int j = 1; j <= n; j++){ if(!used[0][j] && !used[1][j]){ c[0][j] = 1; if(dfs(j,0)){ return true; } } } return false; } void solve(){ cin >> n >> m >> q; for(int i = 0; i < m; i++){ int a,b; cin >> a >> b; edges.pb(mp(a,b)); } bool answer[q]; bool f = true; if(!can(1,0)) f = false; vector<pair<int,int>> Queries[m+1]; for(int i = 0; i < q; i++){ int l,r; cin >> l >> r; if(!f){ cout << "NO\n"; continue; } Queries[l].pb(mp(r,i)); } if(!f) return; for(int i = 0; i <= m; i++){ if(Queries[i].empty()) continue; sort(Queries[i].rbegin(),Queries[i].rend()); if(!can(i,i)){ for(auto&[r,id] : Queries[i]){ answer[id] = 0; } continue; } int L = i, R = m+1; while(R - L > 1){ int mid = (L+R)>>1; if(can(i,mid)) L = mid; else R = mid; } for(auto&[r,id] : Queries[i]){ if(r <= L) answer[id] = 1; else answer[id] = 0; } } for(int i = 0; i < q; i++){ cout << (answer[i] ? "YES" : "NO") << "\n"; } return; } signed main(){ ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr); // init(); int tests = 1; // cin >> tests; for(int test = 1; test <= tests; test++){ // cerr << "test = " << test << "\n"; solve(); } return 0; } /** 6 8 2 1 3 1 5 1 6 2 5 2 6 3 4 3 5 5 6 4 7 4 8 **/

Compilation message (stderr)

Joker.cpp: In function 'bool can(int, int)':
Joker.cpp:52:10: warning: unused variable 'have' [-Wunused-variable]
   52 |     bool have = false;
      |          ^~~~
#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...