제출 #1227224

#제출 시각아이디문제언어결과실행 시간메모리
1227224emad234Joker (BOI20_joker)C++20
39 / 100
2095 ms16064 KiB
#include <bits/stdc++.h> #define ll long long #define F first #define S second #define pii pair<int,int> const ll mxN = 2e5 + 5,mod = 1e9 + 7; using namespace std; vector<vector<pii>>v; int n; int m,q; bool ban[mxN],vis[mxN]; int color[mxN]; bool can; void dfs(int u){ vis[u] = 1; for(auto x : v[u]){ if(ban[x.S]) continue; if(color[x.F] == -1) color[x.F] = !color[u]; if(color[x.F] == color[u]) can = 1; if(!vis[x.F]){ color[x.F] = !color[u]; dfs(x.F); } } } bool solve(int l,int r){ for(int i = 1;i <= n;i++){ vis[i] = 0; color[i] = -1; } for(int i = 1;i <= m;i++){ ban[i] = 0; } can = 0; for(int i = l;i <= r;i++) ban[i] = 1; for(int i = 1;i <= n;i++) if(!vis[i]) dfs(i); return can; } int ans[mxN]; signed main(){ ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); cin >>n>>m>>q; v.resize(n + 4); for(int i = 1;i <= m;i++){ int x,y; cin >>x>>y; v[x].push_back({y,i}); v[y].push_back({x,i}); } for(int i = 1; i <= min(m,1);i++){ // cout<<i<<'\n'; int l = i,r = m + 1; int md; while(l < r){ md = (l + r) / 2; if(!solve(i,md)){ ans[i] = md; r = md; }else l = md + 1; } ans[i] = l; } while(q--){ int l,r; cin >>l>>r; // cout<<ans[l]<<' '; if(l <= 1) cout<<(r < ans[l] ? "YES\n" : "NO\n"); else cout<<(solve(l,r) ? "YES\n" : "NO\n"); } }
#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...