Submission #300401

#	Time	Username	Problem	Language	Result	Execution time	Memory
300401		bacegen4o	Joker (BOI20_joker)	C11	71 / 100	2083 ms	14684 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};
}
int cmpP(const void*pa, const void*pb){
  pair*a = (pair*)pa;
  pair*b = (pair*)pb;
  if(a->first  != b->first) return(a->first  < b->first )?-1:1;
  if(a->second != b->second)return(a->second < b->second)?-1:1;
  return 0;
}

#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

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);
    }
    qsort(v, k, sizeof(pair), cmpP);
    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);
    }
    qsort(v, Q, sizeof(pair), cmpP);
    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:239:13: warning: ignoring return value of 'scanf', declared with attribute warn_unused_result [-Wunused-result]
  239 |             scanf("%d %d", &E[0][i], &E[1][i]);
      |             ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Joker.c:244:13: warning: ignoring return value of 'scanf', declared with attribute warn_unused_result [-Wunused-result]
  244 |             scanf("%d %d", &queries[0][i], &queries[1][i]);
      |             ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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