답안 #719373

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
719373	2023-04-05T21:08:14 Z	Sam_a17	Joker (BOI20_joker)	C++17	25 / 100	90 ms	13016 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) {
    assert(false);
    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({{t, last_bip}, {a, b}});
    return 0;
  }
  
  if(sz[b] > sz[a]) {
    swap(a, b);
  }
 
  int colx = get_color(x), coly = get_color(y);
  int last_bip = bip;
  if(colx == coly) {
    add[b]++;
  }
 
  add[b] -= add[a];
  p[b] = a, sz[a] += sz[b];
  st.push({{t, last_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];
    bip = st.top().first.second;
    st.pop();
  }
}
 
vector<int> lst;
vector<pair<int, int>> edges;
 
int timer = 0;
 
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);
 
  init();
  // rec(1, m, 1, m);

  vector<int> answ(m + 2);

  for(int i = m; i >= 1; i--) {
    merge(edges[i].first, edges[i].second, timer++);
    answ[i] = bip;
  }
 
  //
  for(int i = 1; i <= q; i++) {
    int l, r; cin >> l >> r;

    if(answ[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

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	340 KB	Output is correct
2	Correct	0 ms	340 KB	Output is correct
3	Incorrect	0 ms	340 KB	Output isn't correct
4	Halted	0 ms	0 KB	-

Subtask #2
0 / 8.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	340 KB	Output is correct
2	Correct	0 ms	340 KB	Output is correct
3	Incorrect	0 ms	340 KB	Output isn't correct
4	Halted	0 ms	0 KB	-

Subtask #3
25.0 / 25.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	340 KB	Output is correct
2	Correct	0 ms	340 KB	Output is correct
3	Correct	76 ms	7716 KB	Output is correct
4	Correct	74 ms	12456 KB	Output is correct
5	Correct	88 ms	13004 KB	Output is correct
6	Correct	79 ms	11788 KB	Output is correct
7	Correct	90 ms	11800 KB	Output is correct
8	Correct	72 ms	10688 KB	Output is correct
9	Correct	79 ms	11256 KB	Output is correct
10	Correct	80 ms	12640 KB	Output is correct
11	Correct	85 ms	11664 KB	Output is correct
12	Correct	79 ms	12772 KB	Output is correct
13	Correct	76 ms	10632 KB	Output is correct
14	Correct	80 ms	11320 KB	Output is correct
15	Correct	84 ms	12152 KB	Output is correct
16	Correct	82 ms	13016 KB	Output is correct