Submission #1050412

#	Time	Username	Problem	Language	Result	Execution time	Memory
1050412		duckindog	Joker (BOI20_joker)	C++17	14 / 100	160 ms	15184 KiB

Joker

#include <bits/stdc++.h>

using namespace std;

const int N = 200'000 + 10;
int n, m, q;
vector<pair<int, int>> ad[N];
int co[N];

int32_t main() { 
  cin.tie(0)->sync_with_stdio(0);

  cin >> n >> m >> q;
  for (int i = 1; i <= m; ++i) { 
    int u, v; cin >> u >> v;
    ad[u].push_back({v, i});
    ad[v].push_back({u, i});
  }

  auto color = [&](int st, int l, int r) { 
    bool ret = false;
    co[st] = 1;
    queue<int> q({st});
    while (q.size()) { 
      auto u = q.front(); q.pop();
      for (const auto& [v, id] : ad[u]) { 
        if (l <= id && id <= r) continue;
        if (co[v] == co[u]) return true;
        if (co[v]) continue;
        co[v] = co[u] ^ 3;
        q.push(v);
      }
    }
    return false;
  };
  auto cal = [&](int l, int r) { 
    memset(co, 0, (n + 1) * sizeof(int));
    for (int i = 1; i <= n; ++i) if (!co[i] && color(i, l, r)) return true;
    return false; 
  };

  if (n <= 2000 && q <= 2000) { 
    while (q--) { 
      int l, r; cin >> l >> r;
      cout << (cal(l, r) ? "YES" : "NO") << "\n";
    }
    return 0;
  }

  int l = 1, r = m, ma = -1;
  while (l <= r) { 
    int mid = l + r >> 1;
    if (cal(l, mid)) l = (ma = mid) + 1;
    else r = mid - 1;
  }

  while (q--) { 
    int l, r; cin >> l >> r;
    cout << (r <= ma ? "YES" : "NO") << "\n";
  }
}

Compilation message (stderr)

Joker.cpp: In lambda function:
Joker.cpp:21:10: warning: unused variable 'ret' [-Wunused-variable]
   21 |     bool ret = false;
      |          ^~~
Joker.cpp: In function 'int32_t main()':
Joker.cpp:52:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   52 |     int mid = l + r >> 1;
      |               ~~^~~

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