Submission #858293

#	Time	Username	Problem	Language	Result	Execution time	Memory
858293		Trisanu_Das	Joker (BOI20_joker)	C++17	14 / 100	2056 ms	20208 KiB

Joker

#include <bits/stdc++.h>
using namespace std;
#define ff first
#define ss second
 
int n, m, q;
int vis[200005];
vector<pair<int, int> > adj[200005];
bool ok;
 
void dfs(int u, int p, int c, int l, int r){
  vis[u] = c;
  for(auto v : adj[u]){
    if(v.ff == p || (l <= v.ss && v.ss <= r)) continue;
    if(vis[v.ff] == vis[u]) ok = true;
    if(!vis[v.ff]) dfs(v.ff, u, 3 - c, l, r);
  }
}
 
int main(){
  ios_base::sync_with_stdio(false); cin.tie(NULL);
  cin >> n >> m >> q;
  for(int e = 1; e < m + 1; e++){
    int u, v; cin >> u >> v;
    adj[u].push_back(make_pair(v, e));
    adj[v].push_back(make_pair(u, e));
  }
  while(q--){
    int l, r; cin >> l >> r;
    ok = false;
    memset(vis, 0, sizeof(vis));
    for(int i = 1; i <= n; i++) if(!vis[i]) dfs(i, 0, 1, l, r);
    if(ok) cout << "YES\n";
    else cout << "NO\n";
  }
}

• Subtask 1: 6 / 6
• Subtask 2: 8 / 8
• Subtask 3: 0 / 25
• Subtask 4: 0 / 10
• Subtask 5: 0 / 22
• Subtask 6: 0 / 29