Submission #300405

#	Time	Username	Problem	Language	Result	Execution time	Memory
300405		bacegen4o	Joker (BOI20_joker)	C11	36 / 100	2049 ms	6264 KiB

Joker

#pragma GCC optimize "-O3"
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<math.h>
#include<assert.h>
#include<stdbool.h>
#include<limits.h>
#define swap(a,b) do{ __typeof(a) tp; tp=a; a=b; b=tp; }while(0)
typedef struct{
  int first, second;
}pair;
pair newpair(int a, int b){
  return(pair){a,b};
}

#ifndef STB_STRETCHY_BUFFER_H_INCLUDED
#define STB_STRETCHY_BUFFER_H_INCLUDED
#ifndef NO_STRETCHY_BUFFER_SHORT_NAMES
#define sb_free   stb_sb_free
#define sb_push   stb_sb_push
#define sb_count  stb_sb_count
#define sb_add    stb_sb_add
#define sb_last   stb_sb_last
#endif
#define stb_sb_free(a)         ((a) ? free(stb__sbraw(a)),0 : 0)
#define stb_sb_push(a,v)       (stb__sbmaybegrow(a,1), (a)[stb__sbn(a)++] = (v))
#define stb_sb_count(a)        ((a) ? stb__sbn(a) : 0)
#define stb_sb_add(a,n)        (stb__sbmaybegrow(a,n), stb__sbn(a)+=(n), &(a)[stb__sbn(a)-(n)])
#define stb_sb_last(a)         ((a)[stb__sbn(a)-1])
#define stb__sbraw(a) ((int *) (a) - 2)
#define stb__sbm(a)   stb__sbraw(a)[0]
#define stb__sbn(a)   stb__sbraw(a)[1]
#define stb__sbneedgrow(a,n)  ((a)==0 || stb__sbn(a)+(n) >= stb__sbm(a))
#define stb__sbmaybegrow(a,n) (stb__sbneedgrow(a,(n)) ? stb__sbgrow(a,n) : 0)
#define stb__sbgrow(a,n)      (*((void **)&(a)) = stb__sbgrowf((a), (n), sizeof(*(a))))

static void*stb__sbgrowf(void*arr, int increment, int itemsize){
  int dbl_cur = arr ? 2*stb__sbm(arr) : 0;
  int min_needed = stb_sb_count(arr) + increment;
  int m = dbl_cur > min_needed ? dbl_cur : min_needed;
  int*p = (int *) realloc(arr ? stb__sbraw(arr) : 0, itemsize * m + sizeof(int)*2);
  if(p){
    if(!arr)
      p[1] = 0;
    p[0] = m;
    return p+2;
  } 
  else {
    #ifdef STRETCHY_BUFFER_OUT_OF_MEMORY
    STRETCHY_BUFFER_OUT_OF_MEMORY;
    #endif
    return(void*)(2*sizeof(int));
  }
}
#endif


#if 1//stb
#define STB_(prefix,name)     stb__##prefix##name
#define stb_declare_sort(FUNCNAME, TYPE)    \
                       void FUNCNAME(TYPE *p, int n)
#define stb_define_sort(FUNCNAME,TYPE,COMPARE) \
                       stb__define_sort(       void, FUNCNAME,TYPE,COMPARE)
#define stb_define_sort_static(FUNCNAME,TYPE,COMPARE) \
                       stb__define_sort(static void, FUNCNAME,TYPE,COMPARE)
#define stb__define_sort(MODE, FUNCNAME, TYPE, COMPARE)                       \
                                                                              \
static void STB_(FUNCNAME,_ins_sort)(TYPE *p, int n)                          \
{                                                                             \
   int i,j;                                                                   \
   for (i=1; i < n; ++i) {                                                    \
      TYPE t = p[i], *a = &t;                                                 \
      j = i;                                                                  \
      while (j > 0) {                                                         \
         TYPE *b = &p[j-1];                                                   \
         int c = COMPARE;                                                     \
         if (!c) break;                                                       \
         p[j] = p[j-1];                                                       \
         --j;                                                                 \
      }                                                                       \
      if (i != j)                                                             \
         p[j] = t;                                                            \
   }                                                                          \
}                                                                             \
                                                                              \
static void STB_(FUNCNAME,_quicksort)(TYPE *p, int n)                         \
{                                                                             \
   /* threshold for transitioning to insertion sort */                       \
   while (n > 12) {                                                           \
      TYPE *a,*b,t;                                                           \
      int c01,c12,c,m,i,j;                                                    \
                                                                              \
      /* compute median of three */                                           \
      m = n >> 1;                                                             \
      a = &p[0];                                                              \
      b = &p[m];                                                              \
      c = COMPARE;                                                            \
      c01 = c;                                                                \
      a = &p[m];                                                              \
      b = &p[n-1];                                                            \
      c = COMPARE;                                                            \
      c12 = c;                                                                \
      /* if 0 >= mid >= end, or 0 < mid < end, then use mid */                \
      if (c01 != c12) {                                                       \
         /* otherwise, we'll need to swap something else to middle */         \
         int z;                                                               \
         a = &p[0];                                                           \
         b = &p[n-1];                                                         \
         c = COMPARE;                                                         \
         /* 0>mid && mid<n:  0>n => n; 0<n => 0 */                            \
         /* 0<mid && mid>n:  0>n => 0; 0<n => n */                            \
         z = (c == c12) ? 0 : n-1;                                            \
         t = p[z];                                                            \
         p[z] = p[m];                                                         \
         p[m] = t;                                                            \
      }                                                                       \
      /* now p[m] is the median-of-three */                                   \
      /* swap it to the beginning so it won't move around */                  \
      t = p[0];                                                               \
      p[0] = p[m];                                                            \
      p[m] = t;                                                               \
                                                                              \
      /* partition loop */                                                    \
      i=1;                                                                    \
      j=n-1;                                                                  \
      for(;;) {                                                               \
         /* handling of equality is crucial here */                           \
         /* for sentinels & efficiency with duplicates */                     \
         b = &p[0];                                                           \
         for (;;++i) {                                                        \
            a=&p[i];                                                          \
            c = COMPARE;                                                      \
            if (!c) break;                                                    \
         }                                                                    \
         a = &p[0];                                                           \
         for (;;--j) {                                                        \
            b=&p[j];                                                          \
            c = COMPARE;                                                      \
            if (!c) break;                                                    \
         }                                                                    \
         /* make sure we haven't crossed */                                   \
         if (i >= j) break;                                                   \
         t = p[i];                                                            \
         p[i] = p[j];                                                         \
         p[j] = t;                                                            \
                                                                              \
         ++i;                                                                 \
         --j;                                                                 \
      }                                                                       \
      /* recurse on smaller side, iterate on larger */                        \
      if (j < (n-i)) {                                                        \
         STB_(FUNCNAME,_quicksort)(p,j);                                       \
         p = p+i;                                                             \
         n = n-i;                                                             \
      } else {                                                                \
         STB_(FUNCNAME,_quicksort)(p+i, n-i);                                  \
         n = j;                                                               \
      }                                                                       \
   }                                                                          \
}                                                                             \
                                                                              \
MODE FUNCNAME(TYPE *p, int n)                                                 \
{                                                                             \
   STB_(FUNCNAME, _quicksort)(p, n);                                           \
   STB_(FUNCNAME, _ins_sort)(p, n);                                            \
}
#endif


stb_define_sort(sort_f, pair, a->first==b->first? a->second < b->second : a->first < b->first)

inline double sqrt(double x){
  __asm__ ("fsqrt" : "+t" (x));
  return x;
}
inline int max(int a,int b){return a>b?a:b;}
///////////////////////////////////
enum{MAXN = 200005};
enum{MAXM = 200005};
enum{MAXQ = 200005};
int comp[MAXN], h[MAXN];
bool col_switch[MAXN];
int n_mem, mem_cv[MAXM], mem_cu[MAXM], mem_hcu[MAXM];
bool mem_swcv[MAXM];
int N, M, Q;
int E[2][MAXM], queries[2][MAXQ], res[MAXQ];
int*inds;


void init_dsu(int n){
    for(int i=0; i<n; i++){
        comp[i] = i;
        h[i] = 0;
        col_switch[i] = 0;
    }
    n_mem = 0;
}
pair find(int v){
    bool col = col_switch[v];
    while(comp[v] != v){
        v = comp[v];
        col ^= 1;
        col ^= col_switch[v];
    }
    return newpair(v, col);
}
void merge(int v, int u){
    pair ansv = find(v),
         ansu = find(u);
    int cv = ansv.first,
        cu = ansu.first;
    bool colv = ansv.second,
         colu = ansu.second;
    if(cv != cu){
        if(h[cv] > h[cu]){
            swap(cv, cu);
            swap(v, u);
        }
        mem_cv  [n_mem] = cv;
        mem_cu  [n_mem] = cu;
        mem_hcu [n_mem] = h[cu];
        mem_swcv[n_mem] = col_switch[cv];
        n_mem++;
        comp[cv] = cu;
        if(h[cv] == h[cu])
           h[cu]++;
        col_switch[cv] = (colv != colu);
    }
    else{
        mem_cv[n_mem] = -1;
        n_mem++;
    }
}
int check(int v, int u){
    pair ansv = find(v),
         ansu = find(u);
    int cv = ansv.first,
        cu = ansu.first;
    bool colv = ansv.second,
         colu = ansu.second;
    if(cv != cu)
        return 2;
    if(colv == colu)
        return -1;
    return 1;
}
void rollback(int k){
    while(k--){
        n_mem--;
        int cv = mem_cv[n_mem],
            cu = mem_cu[n_mem];
        bool swcv = mem_swcv[n_mem];
        if(cv == -1)
            continue;
        comp[cv] = cv;
        h[cu] = cu;
        col_switch[cv] = swcv;
    }
}
void solve_for_inds(int e_left_next){
    int k = sb_count(inds);
    pair v[k];
    for(int i=0; i<k; i++){
        int ind = inds[i];
        v[i] = newpair(-queries[1][ind], ind);
    }
    sort_f(v, k);
    int e_right_next = M-1, steps = 0;
    bool got_cycle = false;
    for(int i = 0; i < k; i++){
        int ind = v[i].second;
        int L = queries[0][ind], R = queries[1][ind];
        if(!got_cycle){
            while(e_right_next > R){
                int status = check(E[0][e_right_next], E[1][e_right_next]);
                if(status == -1){
                    got_cycle = true;
                    break;
                }
                merge(E[0][e_right_next], E[1][e_right_next]);
                e_right_next--;
                steps++;
            }
        }
        bool got_cycle_inner = got_cycle;
        int steps_inner = 0;
        if(!got_cycle_inner){
            for (int e = e_left_next; e < L; e++) {
                int status = check(E[0][e], E[1][e]);
                if(status == -1){
                    got_cycle_inner = true;
                    break;
                }
                merge(E[0][e], E[1][e]);
                steps_inner++;
            }
        }
        res[ind] = (int)(got_cycle || got_cycle_inner);
        rollback(steps_inner);
    }
    rollback(steps);
}
void solve(){
    int B = max((int)(M / sqrt(Q)), 1);
    pair v[Q];
    for(int i = 0; i < Q; i++){
        v[i] = newpair(queries[0][i] / B, i);
    }
    sort_f(v, Q);
    init_dsu(N);
    int e_left_next = 0;
    bool got_cycle = false;
    if(inds)
        sb_free(inds);
    inds = NULL;
    for(int i=0; i<Q; i++){
        sb_push(inds, v[i].second);
        if(i + 1 == Q || v[i].first != v[i+1].first){
            while(!got_cycle && e_left_next < v[i].first * B){
                int status = check(E[0][e_left_next], E[1][e_left_next]);
                if(status == -1){
                    got_cycle = true;
                    break;
                }
                merge(E[0][e_left_next], E[1][e_left_next]);
                e_left_next++;
            }
            if(got_cycle){
                for(int j = 0; j<sb_count(inds); j++){
                    int ind = inds[j];
                    res[ind] = 1;
                }
            }
            else{
                solve_for_inds(e_left_next);
            }
            if(inds)
                sb_free(inds);
            inds = NULL;
        }
    }
}
int main(){
    while(scanf("%d%d%d", &N, &M, &Q)==3){
        for(int i = 0; i < M; i++){
            scanf("%d %d", &E[0][i], &E[1][i]);
            E[0][i]--;
            E[1][i]--;
        }
        for(int i = 0; i < Q; i++){
            scanf("%d %d", &queries[0][i], &queries[1][i]);
            queries[0][i]--;
            queries[1][i]--;
        }
        solve();
        for(int i = 0; i < Q; i++){
            if (res[i])
                puts("YES");
            else
                puts("NO");
        }
    }
    return 0;
}

Compilation message (stderr)

Joker.c: In function 'main':
Joker.c:347:13: warning: ignoring return value of 'scanf', declared with attribute warn_unused_result [-Wunused-result]
  347 |             scanf("%d %d", &E[0][i], &E[1][i]);
      |             ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Joker.c:352:13: warning: ignoring return value of 'scanf', declared with attribute warn_unused_result [-Wunused-result]
  352 |             scanf("%d %d", &queries[0][i], &queries[1][i]);
      |             ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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