Submission #719399

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
719399	2023-04-05T21:32:07 Z	Sam_a17	Joker (BOI20_joker)	C++17	25 / 100	88 ms	8292 KB

Joker

#define _CRT_SECURE_NO_WARNINGS
#include <bits/stdc++.h>
//#include "temp.cpp"
#include <cstdio>
using namespace std;
 
#ifndef ONLINE_JUDGE
#define dbg(x) cerr << #x <<" "; print(x); cerr << endl;
#else
#define dbg(x)
#endif
 
#define sz(x) (int((x).size()))
#define len(x) (int)x.length()
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define clr(x) (x).clear()
#define uniq(x) x.resize(unique(all(x)) - x.begin());
#define blt(x) __builtin_popcount(x)
 
#define pb push_back
#define popf pop_front
#define popb pop_back
 
void print(long long t) {cerr << t;}
void print(int t) {cerr << t;}
void print(string t) {cerr << t;}
void print(char t) {cerr << t;}
void print(double t) {cerr << t;}
void print(long double t) {cerr << t;}
void print(unsigned long long t) {cerr << t;}
 
template <class T, class V> void print(pair <T, V> p);
template <class T> void print(vector <T> v);
template <class T> void print(set <T> v);
template <class T, class V> void print(map <T, V> v);
template <class T> void print(multiset <T> v);
template <class T, class V> void print(T v[],V n) {cerr << "["; for(int i = 0; i < n; i++) {print(v[i]); cerr << " "; } cerr << "]";}
template <class T, class V> void print(pair <T, V> p) {cerr << "{"; print(p.first); cerr << ","; print(p.second); cerr << "}";}
template <class T> void print(vector <T> v) {cerr << "[ "; for (T i : v) {print(i); cerr << " ";} cerr << "]";}
template <class T> void print(deque <T> v) {cerr << "[ "; for (T i : v) {print(i); cerr << " ";} cerr << "]";}
template <class T> void print(set <T> v) {cerr << "[ "; for (T i : v) {print(i); cerr << " ";} cerr << "]";}
template <class T> void print(multiset <T> v) {cerr << "[ "; for (T i : v) {print(i); cerr << " ";} cerr << "]";}
template <class T, class V> void print(map <T, V> v) {cerr << "[ "; for (auto i : v) {print(i); cerr << " ";} cerr << "]";}
 
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
#define nl '\n'
 
// for grid problems
int dx[8] = {-1,0,1,0,1,-1,1,-1};
int dy[8] = {0,1,0,-1,1,1,-1,-1};
 
// lowest / (1 << 17) >= 1e5 / (1 << 18) >= 2e5 / (1 << 21) >= 1e6
void fastIO() {
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr); cout.tie(nullptr);
}
// file in/out
void setIO(string str = "") {
  fastIO();
 
  if (str != "") {
    freopen((str + ".in").c_str(), "r", stdin);
    freopen((str + ".out").c_str(), "w", stdout);
  }
}
// Indexed Set
template <class T> using Tree = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
const int N = 2e5 + 10;
int n, m, q, last[N];
int p[N], sz[N], add[N];
int bip;
 
stack<pair<pair<int, int>, pair<int, int>>> st;
 
 
// dsu
void init() {
  bip = 0;
  for(int i = 1; i <= n; i++) {
    p[i] = i, sz[i] = 1;
    add[i] = 0;
  }
}
 
int find(int a) {
  if(a != p[a]) {
    return find(p[a]);
  }
  return p[a];
}
 
int find_sum(int a) {
  if(a != p[a]) {
    return add[a] + find_sum(p[a]);
  }
  return add[a];
}
 
int same(int a, int b) {
  if(find(a) == find(b)) {
    return 1;
  }
  return 0;
}
 
int get_color(int node) {
  int sx = find_sum(node);
  int colx = 1;
  if(sx % 2) colx = 2;
  return colx;
}
 
int merge(int a, int b, int t) {
  if(a == -1) {
    return 0;
  }
 
  int x = a, y = b;
  a = find(a), b = find(b);
 
  if(same(a, b)) {
    int colx = get_color(x), coly = get_color(y);
    int last_bip = bip;
    if(colx == coly) {
      bip = 1;
    }
    st.push({{0, last_bip}, {a, b}});
    return 0;
  }
  
  if(sz[b] > sz[a]) {
    swap(a, b);
  }
 
  int colx = get_color(x), coly = get_color(y);
  int okk = 0;
  if(colx == coly) {
    add[b]++;
    okk++;
  }
 
  add[b] -= add[a];
  p[b] = a, sz[a] += sz[b];
  st.push({{okk, bip}, {a, b}});
  return 1;
}
 
void rollback() {
  if (!st.empty()) {
    auto u = st.top().second;
    int a = u.first, b = u.second;
    sz[a] -= sz[b], p[b] = b;
    add[b] += add[a];
    add[b] -= st.top().first.first;
    bip = st.top().first.second;
    st.pop();
  }
}
 
vector<int> lst;
vector<pair<int, int>> edges;
 
int timer = 0;

bool answ[305][N];

void rec(int l, int r, int L, int R) {
  if(l > r) {
    return;
  }
 
  int mid = (l + r) / 2;
 
  for(int i = l; i < mid; i++) {
    merge(edges[i].first, edges[i].second, timer++);
  }
 
  int opt = R + 1;
  for(int i = R; i >= L && i >= mid; i--) {
    merge(edges[i].first, edges[i].second, timer++);
    if(bip || i == mid) {
      opt = i;
      rollback();
      break;
    }
  }
 
  last[mid] = opt;
  opt = min(opt, R);
 
  for(int i = R; i > opt; i--) {
    rollback();
  }
 
  for(int i = l; i < mid; i++) {
    rollback();
  }
 
  for(int i = R; i > opt; i--) {
    merge(edges[i].first, edges[i].second, timer++);
  }
 
  rec(l, mid - 1, L, opt);
 
  for(int i = R; i > opt; i--) {
    rollback();
  }
 
  for(int i = l; i <= mid; i++) {
    merge(edges[i].first, edges[i].second, timer++);
  }
 
  rec(mid + 1, r, max(opt, mid + 1), R);
 
  for(int i = l; i <= mid; i++) {
    rollback();
  }
}
 
void solve_() {
  cin >> n >> m >> q;
 
  edges.emplace_back(-1, -1);
  for(int i = 1; i <= m; i++) {
    int a, b; cin >> a >> b;
    edges.emplace_back(a, b);
  }
  edges.emplace_back(-1, -1);
 
  // rec(1, m, 1, m);
  init();
  for(int j = 1; j <= min(m, 1); j++) {

    if(j - 1 >= 1) { 
      merge(edges[j - 1].first, edges[j - 1].second, timer++);
    }

    answ[j][m + 1] = bip;
    int cnt = 0;
    for(int i = m; i >= j; i--) {
      if(!bip) {
        cnt++;
        merge(edges[i].first, edges[i].second, timer++);
      }
      answ[j][i] = bip;
    }

    for(int i = 1; i <= cnt; i++) {
      rollback();
    }
  }
 
  //
  for(int i = 1; i <= q; i++) {
    int l, r; cin >> l >> r;

    if(answ[l][r + 1]) {
      cout << "YES" << '\n';
    } else {
      cout << "NO" << '\n';
    }
  }
 
}
 
int main() {
  setIO();
 
  auto solve = [&](int test_case)-> void {
    while(test_case--) {
      solve_();
    }
  };
 
  int test_cases = 1;
  // cin >> test_cases;
  solve(test_cases);
 
  return 0;
}

Compilation message

Joker.cpp: In function 'void setIO(std::string)':
Joker.cpp:64:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   64 |     freopen((str + ".in").c_str(), "r", stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Joker.cpp:65:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   65 |     freopen((str + ".out").c_str(), "w", stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 6.0

#	Verdict	Memory	Grader output
1	Correct	340 KB	Output is correct
2	Correct	340 KB	Output is correct
3	Incorrect	340 KB	Output isn't correct
4	Halted	0 KB	-

Subtask #2
0 / 8.0

#	Verdict	Memory	Grader output
1	Correct	340 KB	Output is correct
2	Correct	340 KB	Output is correct
3	Incorrect	340 KB	Output isn't correct
4	Halted	0 KB	-

Subtask #3
25.0 / 25.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	340 KB	Output is correct
2	Correct	0 ms	340 KB	Output is correct
3	Correct	71 ms	5456 KB	Output is correct
4	Correct	72 ms	8292 KB	Output is correct
5	Correct	70 ms	5160 KB	Output is correct
6	Correct	88 ms	5444 KB	Output is correct
7	Correct	68 ms	5672 KB	Output is correct
8	Correct	63 ms	5208 KB	Output is correct
9	Correct	67 ms	5616 KB	Output is correct
10	Correct	78 ms	6816 KB	Output is correct
11	Correct	69 ms	5540 KB	Output is correct
12	Correct	71 ms	6392 KB	Output is correct
13	Correct	67 ms	4620 KB	Output is correct
14	Correct	74 ms	5060 KB	Output is correct
15	Correct	84 ms	6024 KB	Output is correct
16	Correct	76 ms	6684 KB	Output is correct