# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
1037442 | wood | Joker (BOI20_joker) | C++17 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
using namespace std;
typedef vector<int> vi;
typedef pair<int,int> p32;
typedef vector<p32> vp32;
#define pb push_back
#define eb emplace_back
#define fi first
#define se second
int main(){
int n,m,q; cin>>n>>m>>q;
vp32 adj[n];
for(int i = 0; i<m; i++){
int a,b; cin>>a>>b;
a--; b--;
adj[a].eb(b,i+1);
adj[b].eb(a,i+1);
}
vp32 querries[200];
for(int j = 0; j<q; j++){
int l,r; cin>>l>>r;
querries[l-1].eb(r,i);
}
int res[n];
memset(res,0,sizeof res);
for(int l = 0; l<200; l++){
sort(querries[l].begin(),querries[l].end());
int left = -1, right = querries[l].size();
while(right-left>1){
int m = (right+left)/2;
int parent[n];
int depth[n];
memset(parent,0,sizeof parent);
memset(depth,0,sizeof depth);
stack<int> qu;
for(int i = 0; i<n; i++){
if(!parent[i]){
parent[i] = i+1;
qu.push(i);
while(!qu.empty()){
int x = qu.top();
depth[x] = depth[parent[x]-1]+1;
qu.pop();
for(p32 tt : adj[x]){
if(tt.se<l||tt.se>querries[l][m].first){
if(depth[tt.fi]&&parent[x]-1!=tt.fi&&((depth[x]-depth[tt.fi]+1)&1)) goto found;
if(parent[tt.fi]==0){
parent[tt.fi] = x+1;
qu.push(tt.fi);
}
}
}
}
}
}
right = m;
continue;
found:
left = m;
}
for(int i = 0; i<=l; i++){
res[querries[l][i].se] = true;
}
}
for(bool x : res) cout<<(x ? "YES" : "NO");
return 0;
}