Submission #300383

#	Time	Username	Problem	Language	Result	Execution time	Memory
300383		bacegen4o	Joker (BOI20_joker)	C11	71 / 100	2032 ms	18780 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;
}

#define pb(zpv, zvv) zpv.ptr = pushback(zpv.ptr, &zpv.sz, zvv)
#define resizeArray(ptr, type, size) ((type*)realloc(ptr, (size) * sizeof(type)))
int *pushback(int *array, int *size, int value) {
    int *output = resizeArray(array, int, *size + 1);
    output[(*size)++] = value;
    return output;
}
typedef struct{
	int*ptr;
	int sz;
}vec;
vec newVec(){
	vec rez;
	rez.ptr = NULL;
	rez.sz  = 0;
	return rez;
}
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];
vec 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 = inds.sz;
    pair v[k];
    for(int i=0; i<k; i++){
        int ind = inds.ptr[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;
    inds = newVec();
    for (int i = 0; i < Q; i++) {
        pb(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 < inds.sz; j++) {
                    int ind = inds.ptr[j];
                    res[ind] = 1;
                }
            }
            else {
                solve_for_inds(e_left_next);
            }
            inds = newVec();
        }
    }
}
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:203:13: warning: ignoring return value of 'scanf', declared with attribute warn_unused_result [-Wunused-result]
  203 |             scanf("%d %d", &E[0][i], &E[1][i]);
      |             ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Joker.c:208:13: warning: ignoring return value of 'scanf', declared with attribute warn_unused_result [-Wunused-result]
  208 |             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