| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 300380 |
2020-09-17T06:25:25 Z |
bacegen4o |
Joker (BOI20_joker) |
C |
|
0 ms |
0 KB |
#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;
}
///////////////////////////////////
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 = fmax((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
Joker.c: In function 'main':
Joker.c:198:13: warning: ignoring return value of 'scanf', declared with attribute warn_unused_result [-Wunused-result]
198 | scanf("%d %d", &E[0][i], &E[1][i]);
| ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Joker.c:203:13: warning: ignoring return value of 'scanf', declared with attribute warn_unused_result [-Wunused-result]
203 | scanf("%d %d", &queries[0][i], &queries[1][i]);
| ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
/tmp/ccqHPxVi.o: In function `solve':
Joker.c:(.text+0x89b): undefined reference to `fmax'
Joker.c:(.text+0xbda): undefined reference to `sqrt'
collect2: error: ld returned 1 exit status
