| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 858297 | Trisanu_Das | Joker (BOI20_joker) | C++17 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include<bits/stdc++.h>
using namespace std;
vector<int> adj[200005];
vector<pair<int, int> > arr[200005];
int color[200005], ans[200005], a[200005], b[200005], n, m, q;
int dfs(int u, int c) {
if(color[u]) {
if(c == color[x]) return 0;
else return 1;
}
color[u] = c;
for(auto v : adj[u]) if(dfs(v, 3 - c)) return 1;
return 0;
}
bool check(int l, int r) {
memset(color, 0, sizeof color);
for(int i = 1; i <= n; i++) adj[i].clear();
for(int i = 0; i < l; i++) adj[a[i]].push_back(b[i]), adj[b[i]].push_back(a[i]);
for(int i = r + 1; i < m; i++) adj[a[i]].push_back(b[i]), adj[b[i]].push_back(a[i]);
for(int i = 0; i < n; i++) if(!color[i]) if(dfs(i, 1)) return 1;
return 0;
}
int main() {
cin.sync_with_stdio(false); cin.tie(NULL);
cin >> n >> m >> q;
for(int i = 0; i < m; i++) cin >> a[i] >> b[i];
for(int e = 0; e < q; e++) {
int l, r;
cin >> l >> r;
arr[l - 1].push_back({r - 1, e});
}
for(int i = 0; i < m; i++) {
sort(arr[i].begin(), arr[i].end());
int l = 0, r = arr[i].size();
while(l < r) {
int mid = l + r >> 1;
if(check(i, arr[i][mid].first)) l = mid + 1;
else r = mid;
}
for(int j = 0; j < l; j++) ans[arr[i][j].second] = 1;
for(int j = l; j < arr[i].size(); j++) ans[arr[i][j].second] = 0;
}
for(int i = 0; i < q; i++) cout << (ans[i] ? "YES\n":"NO\n");
}