This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.io.StreamTokenizer;
public class Joker {
static StreamTokenizer in;
static PrintWriter out;
static int nextInt() throws IOException {
in.nextToken();
return (int) in.nval;
}
final static int MAXN = 200005;
static int[] parent = new int[MAXN * 2];
static int[] size = new int[MAXN * 2];
static int depth = 0;
static int[][] par = new int[20][MAXN * 2];
static int sz[][] = new int[20][MAXN * 2];
static int mem[][] = new int[20][MAXN * 2];
static int cnt[] = new int[20];
static void setParent(int v, int p) {
if (par[depth][v] == 0) {
par[depth][v] = parent[v];
sz[depth][v] = size[v];
mem[depth][cnt[depth]++] = v;
}
parent[v] = p;
}
static int getParent(int v) {
while (parent[v] != v) {
v = parent[v];
}
return v;
}
static boolean mergeSets(int u, int v) {
int pu = getParent(u << 1);
int pv = getParent(v << 1);
boolean res;
if ((pu >> 1) == (pv >> 1)) {
res = (pu % 2) != (pv % 2);
} else {
if (size[pu] > size[pv]) {
int tmp = pu;
pu = pv;
pv = tmp;
}
setParent(pu, pv ^ 1);
size[pv ^ 1] += size[pu];
setParent(pu ^ 1, pv);
size[pv] += size[pu ^ 1];
res = true;
}
return res;
}
static void record() {
depth++;
}
static void rollback() {
for (int i = 0; i < cnt[depth]; i++) {
int v = mem[depth][i];
size[parent[v]] -= sz[depth][v];
parent[v] = par[depth][v];
size[v] = sz[depth][v];
par[depth][v] = 0;
}
cnt[depth] = 0;
depth--;
}
static int n, m, q, a[] = new int[MAXN], b[] = new int[MAXN], l[] = new int[MAXN], r[] = new int[MAXN];
static void init() {
for (int i = 2; i <= 2 * n + 1; i++) {
parent[i] = i;
size[i] = 1;
}
}
static int[] last = new int[MAXN];
static int max(int x, int y) {
return x > y ? x : y;
}
static void rec(int L1, int L2, int R1, int R2) {
record();
int LM = (L1 + L2) / 2;
for (int i = L1; i < LM; i++) {
mergeSets(a[i], b[i]);
}
//^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
record();
for (int i = R2; i >= LM; i--) {
if (!mergeSets(a[i], b[i])) {
last[LM] = i;
break;
}
}
rollback();
//vvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvv
if (LM < L2) {
mergeSets(a[LM], b[LM]);
rec(LM + 1, L2, max(LM + 1, last[LM]), R2);
}
rollback();
//^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
if (L1 < LM) {
record();
boolean good = true;
for (int i = R2; i > last[LM]; i--) {
mergeSets(a[i], b[i]);
}
rec(L1, LM - 1, R1, last[LM]);
rollback();
}
//vvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvv
}
public static void main(String[] args) throws IOException {
in = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
out = new PrintWriter(System.out);
n = nextInt();
m = nextInt();
q = nextInt();
for (int i = 1; i <= m; i++) {
a[i] = nextInt();
b[i] = nextInt();
}
for (int i = 1; i <= q; i++) {
l[i] = nextInt();
r[i] = nextInt();
}
init();
int X = 1;
while (X <= m) {
if (!mergeSets(a[X], b[X])) {
break;
}
X++;
}
init();
for (int i = X + 1; i <= m; i++) {
last[i] = m + 1;
}
if (X <= m) {
rec(1, X, 1, m);
}
for (int i = 1; i <= q; i++) {
out.println(last[l[i]] <= r[i] ? "NO" : "YES");
}
out.flush();
}
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |