Submission #254786

#TimeUsernameProblemLanguageResultExecution timeMemory
254786model_codeJoker (BOI20_joker)Java
61 / 100
2016 ms142904 KiB
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 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...