Submission #719391

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
719391	2023-04-05T21:25:26 Z	Sam_a17	Joker (BOI20_joker)	C++17	25 / 100	91 ms	5464 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;
    }
    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.second, b = u.first;
    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);

  for(int j = 1; j <= min(m, 2); j++) {
    init();
    for(int i = 1; i < j; i++) {
      merge(edges[i].first, edges[i].second, timer++);
    }

    answ[j][m + 1] = bip;
    for(int i = m; i >= j; i--) {
      merge(edges[i].first, edges[i].second, timer++);
      answ[j][i] = bip;
    }
  }
 
  //
  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 'int merge(int, int, int)':
Joker.cpp:125:9: warning: unused variable 'last_bip' [-Wunused-variable]
  125 |     int last_bip = bip;
      |         ^~~~~~~~
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	72 ms	4316 KB	Output is correct
4	Correct	77 ms	5260 KB	Output is correct
5	Correct	91 ms	5220 KB	Output is correct
6	Correct	78 ms	4172 KB	Output is correct
7	Correct	83 ms	4192 KB	Output is correct
8	Correct	78 ms	3884 KB	Output is correct
9	Correct	81 ms	4400 KB	Output is correct
10	Correct	86 ms	5464 KB	Output is correct
11	Correct	82 ms	4140 KB	Output is correct
12	Correct	85 ms	5128 KB	Output is correct
13	Correct	79 ms	3244 KB	Output is correct
14	Correct	85 ms	3740 KB	Output is correct
15	Correct	90 ms	4620 KB	Output is correct
16	Correct	85 ms	5392 KB	Output is correct