Submission #1283430

#	Time	Username	Problem	Language	Result	Execution time	Memory
1283430		repmann	Joker (BOI20_joker)	C++20	14 / 100	945 ms	45292 KiB

Joker

#include <bits/stdc++.h>
using namespace std;
int N, M, K, 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[400001];
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)
{
  for(l += K + 1, r += K + 1; l < r; l >>= 1, r >>= 1)
  {
    if(l & 1) ST[l++].push_back(x);
    if(r & 1) ST[--r].push_back(x);
  }
  return;
}
inline void Setup()
{
  SetupDSU();
//  cout << K << '\n';
  for(int i = K + K + 2; i; i--) ST[i].clear();
  for(int i = 1; i <= M; i++) END[i] = K + 1;
  for(int i = 1, j = 1; i <= K; i++)
  {
    int S = (L[i] + R[i]) >> 1;
    while(j < S) {END[j] = i; j++;}
  }
  for(int i = 1; i <= K; i++) Insert(i, K + 1, i);
  for(int i = 1; i <= M; i++) if(END[i] > 1) Insert(1, END[i], i);
  return;
}
inline void DFS(int i = 1)
{
//  cout << i << ":\n";
  if(i > (K + K + 1)) return;
  int pos0 = pos;
//  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[i - K - 1] + R[i - K - 1]) >> 1;
    if(!bipartite) {L[i - K - 1] = S + 1; O[i - K - 1] = S;}
    else R[i - K - 1] = S - 1;
  }
  else
  {
    DFS(i << 1);
    DFS(i << 1 | 1);
  }
  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;
  }
  K = M;
  for(int i = 1; i <= M; i++)
  {
    if(!O[i]) {L[i] = max(O[0], i); R[i] = M + 1;}
    else {K = min(i - 1, K);}
  }
  while(K >= 1)
  {
    Setup();
//    for(int i = 1; i <= M; i++) cout << i << ": " << L[i] << ' ' << ((L[i] + R[i]) >> 1) << ' ' << R[i] << '\n';
    DFS();
    while(L[K] > R[K]) K--;
  }
//  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