Submission #933204

#	Time	Username	Problem	Language	Result	Execution time	Memory
933204		Erfan1386Y	Joker (BOI20_joker)	C++17	100 / 100	229 ms	13004 KiB

Joker

#include <bits/stdc++.h>
#define file_io freopen("input.txt", "r", stdin);freopen("output.txt", "w", stdout);
#define fast_io ios::sync_with_stdio(false);cin.tie(0);
#define what(x) cerr << #x << " is " << x << '\n';
#define kill(x) {cout << x << endl; continue;}
#define all(x) (x).begin(), (x).end()
#define pii pair<int, int>
#define pb push_back
#define ll long long
#define F first
#define S second
const ll inf = 1e18, mod = 1e9 + 7, delta = 1e9 + 9, SQ = 450, P = 6065621;
 
using namespace std;

const int N = 2e5 + 10, LG = 40;
int par[N], sz[N], col[N], cnt, L, R, ans[N];
vector<pii> st;
pii edges[N];

int root (int &v) {
  int res = 0;
  while (par[v] != v) 
    res ^= col[v], v = par[v];
  return res;
}
void mrg (pii e) {
  auto [v, u] = e;
  int r1 = root(v) , r2 = root(u);
  if (v == u) {
    if (r1 == r2) st.pb(pii(-2 , -2)), cnt++;
    else st.pb(pii(-1 , -1));
    return;
  }
  if (sz[v] < sz[u]) swap(v , u);
  par[u] = v;
  sz[v] += sz[u];
  st.pb(pii(v , u));
  col[u] = r1 ^ r2 ^ 1;
}

void undo() {
  pii e = st.back();
  st.pop_back();
  if(e.F == -1) return;
  if(e.F == -2) {--cnt; return;}
  col[e.S] = 0;
  par[e.S] = e.S;
  sz[e.F] -= sz[e.S];
}

void solve (int a, int b, int x, int y) {
  if (a > b) return;
  int save = st.size();
  int mid = (a + b) >> 1;
  while (L < mid) mrg(edges[L++]);
  while (R > mid && !cnt) mrg(edges[R--]);
  ans[mid] = R;
  if (cnt == 0) ans[mid]--;
  while (st.size() > save) undo();
  L = a, R = y;
  while (L <= mid) mrg(edges[L++]);
  solve(mid + 1, b, ans[mid], y);
  while (st.size() > save) undo();
  L = a, R = y;
  while (R > ans[mid]) mrg(edges[R--]);
  solve(a, mid - 1, x, ans[mid]);
  while (st.size() > save) undo();
  L = a, R = y;
}

int main () {
  fast_io;
  int n, m, q;
  cin >> n >> m >> q;
  L = 1, R = m;
  fill(sz + 1, sz + n + 1, 1);
  iota(par + 1, par + n + 1, 1);
  for (int i = 1; i <= m; i++) {
    cin >> edges[i].F >> edges[i].S;
  }
  solve(1, m, 1, m);
  while (q--) {
    int l, r;
    cin >> l >> r;
    if (r > ans[l]) cout << "NO\n";
    else cout << "YES\n";
  }
  return 0;
}

Compilation message (stderr)

Joker.cpp: In function 'void solve(int, int, int, int)':
Joker.cpp:60:20: warning: comparison of integer expressions of different signedness: 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   60 |   while (st.size() > save) undo();
      |          ~~~~~~~~~~^~~~~~
Joker.cpp:64:20: warning: comparison of integer expressions of different signedness: 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   64 |   while (st.size() > save) undo();
      |          ~~~~~~~~~~^~~~~~
Joker.cpp:68:20: warning: comparison of integer expressions of different signedness: 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   68 |   while (st.size() > save) undo();
      |          ~~~~~~~~~~^~~~~~

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