제출 #1283308

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1283308		repmann	Joker (BOI20_joker)	C++20	14 / 100	2097 ms	59228 KiB

Joker

#include <bits/stdc++.h>
using namespace std;
int N, M, K, B, Q;
int U[200001], V[200001];
int L[200001], R[200001], O[200001];
int END[200001];
struct Node
{
  int p, r;
  bool w;
}DSU[200001];
bool bipartite;
struct Delta
{
  int i;
  Node u;
}D[400001];
int pos;
vector <int> ST[800001];
inline void SetupDSU()
{
  pos = 0;
  bipartite = 1;
  for(int i = 1; i <= N; i++) DSU[i] = {i, 0, 0};
  return;
}
inline void Rollback(int pos0)
{
  while(pos > pos0)
  {
    if(D[pos].i) DSU[D[pos].i] = D[pos].u;
    else bipartite = 1;
    pos--;
  }
  return;
}
inline int Find(int u)
{
  while(u != DSU[u].p) u = DSU[u].p;
  return u;
}
inline bool Path(int u)
{
  bool w = 0;
  while(u != DSU[u].p) {w ^= DSU[u].w; u = DSU[u].p;}
  return w;
}
inline void Union(int u, int v)
{
  bool uw = Path(u);
  u = Find(u);
  bool vw = Path(v);
  v = Find(v);
  if(u == v)
  {
    if(bipartite && (uw == vw)) {D[++pos] = {0, DSU[0]}; bipartite = 0;}
    return;
  }
  if(DSU[u].r < DSU[v].r) swap(u, v);
  if(DSU[u].r == DSU[v].r)
  {
    D[++pos] = {u, DSU[u]};
    DSU[u].r++;
  }
  D[++pos] = {v, DSU[v]};
  DSU[v].p = u;
  DSU[v].w = uw ^ vw ^ 1;
  return;
}
inline void Insert(int L, int R, int X, int i = 1, int LC = 1, int RC = K)
{
  if((LC > R) || (L > RC)) return;
  if((L <= LC) && (RC <= R)) {ST[i].push_back(X); return;}
  int S = (LC + RC) >> 1;
  Insert(L, R, X, i << 1, LC, S);
  Insert(L, R, X, i << 1 | 1, S + 1, RC);
  return;
}
inline void Setup()
{
  SetupDSU();
  K = 1;
  while(K < B) K <<= 1;
  for(int i = 1; i < (K + B); i++) ST[i] = vector <int>();
  for(int i = 1; i <= M; i++) END[i] = B + 1;
  for(int i = 1, j = 1; i <= B; i++)
  {
    int S = (L[i] + R[i]) >> 1;
    while(j < S) {END[j] = i; j++;}
  }
  for(int i = 1; i <= B; i++) Insert(i, B, i);
  for(int i = 1; i <= M; i++) if(END[i] > 1) Insert(1, END[i] - 1, i);
  return;
}
inline void DFS(int i = 1, int LC = 1, int RC = K)
{
  if(LC > B) return;
  int pos0 = pos;
//  cout << i << ":\n";
//  for(int x : ST[i]) cout << x << '\n';
  for(int j = 0; bipartite && (j < ST[i].size()); j++) Union(U[ST[i][j]], V[ST[i][j]]);
  if(i >= K)
  {
    int S = (L[LC] + R[LC]) >> 1;
    if(!bipartite) {L[LC] = S + 1; O[LC] = S;}
    else R[LC] = S - 1;
  }
  else
  {
    int S = (LC + RC) >> 1;
    DFS(i << 1, LC, S);
    DFS(i << 1 | 1, S + 1, RC);
  }
  Rollback(pos0);
  return;
}
int main()
{
  ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
  cin >> N >> M >> Q;
  for(int i = 1; i <= M; i++) cin >> U[i] >> V[i];
  SetupDSU();
  for(int i = M; i >= 1; i--)
  {
    Union(U[i], V[i]);
    if(!bipartite) {O[0] = i; break;}
  }
  SetupDSU();
  for(int i = 1; i <= M; i++)
  {
    if(bipartite) Union(U[i], V[i]);
    if(!bipartite) O[i] = M + 1;
  }
  B = M;
  for(int i = 1; i <= M; i++)
  {
    if(!O[i]) {L[i] = max(O[0], i); R[i] = M + 1;}
    else {B = min(i - 1, B);}
  }
  while(B >= 1)
  {
//    for(int i = 1; i <= M; i++)
//    {
//      int S = (L[i] + R[i]) >> 1;
//      cout << i << ": " << L[i] << ' ' << S << ' ' << R[i] << '\n';
//    }
    Setup();
//    for(int i = 1; i <= M; i++) cout << i << ": " << END[i] << '\n';
    DFS();
//    for(int i = 1; i <= M; i++)
//    {
//      int S = (L[i] + R[i]) >> 1;
//      cout << i << ": " << L[i] << ' ' << S << ' ' << R[i] << ' ' << O[i] << '\n';
//    }
    while(L[B] > R[B]) B--;
  }
//  for(int i = 0; i <= M; i++) cout << i << ": " << O[i] << '\n';
  int l, r;
  for(int i = 1; i <= Q; i++)
  {
    cin >> l >> r;
    if((r + 1) <= O[l - 1]) cout << "YES\n";
    else cout << "NO\n";
  }

  return 0;
}

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