Submission #300405

#TimeUsernameProblemLanguageResultExecution timeMemory
300405bacegen4oJoker (BOI20_joker)C11
36 / 100
2049 ms6264 KiB
#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]);
      |             ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...