oj.uz

Submission #254786

# Submission time Handle Problem Language Result Execution time Memory
254786 2020-07-30T15:21:02 Z model_code Joker (BOI20_joker) Java 11
61 / 100
 2000 ms 142904 KB 
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();
    }
}

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 261 ms 118972 KB Output is correct
2 Correct 269 ms 119112 KB Output is correct
3 Correct 329 ms 119004 KB Output is correct
4 Correct 234 ms 118884 KB Output is correct
5 Correct 270 ms 119048 KB Output is correct
6 Correct 333 ms 119188 KB Output is correct
7 Correct 246 ms 119652 KB Output is correct
8 Correct 243 ms 120180 KB Output is correct
9 Correct 219 ms 120260 KB Output is correct
10 Correct 173 ms 120276 KB Output is correct
11 Correct 196 ms 120288 KB Output is correct
12 Correct 173 ms 120332 KB Output is correct
13 Correct 213 ms 120104 KB Output is correct
14 Correct 336 ms 119860 KB Output is correct
15 Correct 188 ms 120168 KB Output is correct
16 Correct 174 ms 120152 KB Output is correct
17 Correct 217 ms 120536 KB Output is correct
18 Correct 175 ms 119912 KB Output is correct
19 Correct 194 ms 120128 KB Output is correct
20 Correct 271 ms 120252 KB Output is correct
21 Correct 245 ms 120200 KB Output is correct
22 Correct 233 ms 120288 KB Output is correct
23 Correct 228 ms 120276 KB Output is correct
24 Correct 280 ms 120108 KB Output is correct
25 Correct 312 ms 120084 KB Output is correct
26 Correct 183 ms 120160 KB Output is correct
27 Correct 185 ms 119140 KB Output is correct
28 Correct 224 ms 120164 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 261 ms 118972 KB Output is correct
2 Correct 269 ms 119112 KB Output is correct
3 Correct 329 ms 119004 KB Output is correct
4 Correct 234 ms 118884 KB Output is correct
5 Correct 270 ms 119048 KB Output is correct
6 Correct 333 ms 119188 KB Output is correct
7 Correct 246 ms 119652 KB Output is correct
8 Correct 243 ms 120180 KB Output is correct
9 Correct 219 ms 120260 KB Output is correct
10 Correct 173 ms 120276 KB Output is correct
11 Correct 196 ms 120288 KB Output is correct
12 Correct 173 ms 120332 KB Output is correct
13 Correct 213 ms 120104 KB Output is correct
14 Correct 336 ms 119860 KB Output is correct
15 Correct 188 ms 120168 KB Output is correct
16 Correct 174 ms 120152 KB Output is correct
17 Correct 217 ms 120536 KB Output is correct
18 Correct 175 ms 119912 KB Output is correct
19 Correct 194 ms 120128 KB Output is correct
20 Correct 271 ms 120252 KB Output is correct
21 Correct 245 ms 120200 KB Output is correct
22 Correct 233 ms 120288 KB Output is correct
23 Correct 228 ms 120276 KB Output is correct
24 Correct 280 ms 120108 KB Output is correct
25 Correct 312 ms 120084 KB Output is correct
26 Correct 183 ms 120160 KB Output is correct
27 Correct 185 ms 119140 KB Output is correct
28 Correct 224 ms 120164 KB Output is correct
29 Correct 221 ms 120812 KB Output is correct
30 Correct 263 ms 121472 KB Output is correct
31 Correct 330 ms 121056 KB Output is correct
32 Correct 318 ms 120616 KB Output is correct
33 Correct 284 ms 121180 KB Output is correct
34 Correct 234 ms 121780 KB Output is correct
35 Correct 317 ms 122124 KB Output is correct
36 Correct 259 ms 121404 KB Output is correct
37 Correct 267 ms 122704 KB Output is correct
38 Correct 231 ms 121644 KB Output is correct
39 Correct 268 ms 120940 KB Output is correct
40 Correct 233 ms 120612 KB Output is correct
41 Correct 250 ms 121512 KB Output is correct
42 Correct 443 ms 121316 KB Output is correct
43 Correct 404 ms 121564 KB Output is correct
44 Correct 432 ms 121068 KB Output is correct
45 Correct 245 ms 121644 KB Output is correct
46 Correct 342 ms 121356 KB Output is correct
47 Correct 467 ms 121456 KB Output is correct
48 Correct 274 ms 121712 KB Output is correct
49 Correct 339 ms 121556 KB Output is correct
50 Correct 281 ms 122164 KB Output is correct
51 Correct 336 ms 121308 KB Output is correct
52 Correct 339 ms 121148 KB Output is correct
53 Correct 317 ms 121588 KB Output is correct
54 Correct 298 ms 122108 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 261 ms 118972 KB Output is correct
2 Correct 269 ms 119112 KB Output is correct
3 Correct 1707 ms 140060 KB Output is correct
4 Correct 596 ms 123984 KB Output is correct
5 Correct 1014 ms 124088 KB Output is correct
6 Correct 1423 ms 137788 KB Output is correct
7 Correct 1319 ms 141552 KB Output is correct
8 Correct 1487 ms 142764 KB Output is correct
9 Correct 1494 ms 142904 KB Output is correct
10 Correct 1197 ms 123740 KB Output is correct
11 Correct 1996 ms 141968 KB Output is correct
12 Correct 1268 ms 124228 KB Output is correct
13 Correct 1269 ms 137964 KB Output is correct
14 Correct 1422 ms 142368 KB Output is correct
15 Correct 1855 ms 142668 KB Output is correct
16 Correct 1515 ms 125964 KB Output is correct

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 261 ms 118972 KB Output is correct
2 Correct 269 ms 119112 KB Output is correct
3 Correct 329 ms 119004 KB Output is correct
4 Correct 234 ms 118884 KB Output is correct
5 Correct 270 ms 119048 KB Output is correct
6 Correct 333 ms 119188 KB Output is correct
7 Correct 246 ms 119652 KB Output is correct
8 Correct 243 ms 120180 KB Output is correct
9 Correct 219 ms 120260 KB Output is correct
10 Correct 173 ms 120276 KB Output is correct
11 Correct 196 ms 120288 KB Output is correct
12 Correct 173 ms 120332 KB Output is correct
13 Correct 213 ms 120104 KB Output is correct
14 Correct 336 ms 119860 KB Output is correct
15 Correct 188 ms 120168 KB Output is correct
16 Correct 174 ms 120152 KB Output is correct
17 Correct 217 ms 120536 KB Output is correct
18 Correct 175 ms 119912 KB Output is correct
19 Correct 194 ms 120128 KB Output is correct
20 Correct 271 ms 120252 KB Output is correct
21 Correct 245 ms 120200 KB Output is correct
22 Correct 233 ms 120288 KB Output is correct
23 Correct 228 ms 120276 KB Output is correct
24 Correct 280 ms 120108 KB Output is correct
25 Correct 312 ms 120084 KB Output is correct
26 Correct 183 ms 120160 KB Output is correct
27 Correct 185 ms 119140 KB Output is correct
28 Correct 224 ms 120164 KB Output is correct
29 Correct 1707 ms 140060 KB Output is correct
30 Correct 596 ms 123984 KB Output is correct
31 Correct 1014 ms 124088 KB Output is correct
32 Correct 1423 ms 137788 KB Output is correct
33 Correct 1319 ms 141552 KB Output is correct
34 Correct 1487 ms 142764 KB Output is correct
35 Correct 1494 ms 142904 KB Output is correct
36 Correct 1197 ms 123740 KB Output is correct
37 Correct 1996 ms 141968 KB Output is correct
38 Correct 1268 ms 124228 KB Output is correct
39 Correct 1269 ms 137964 KB Output is correct
40 Correct 1422 ms 142368 KB Output is correct
41 Correct 1855 ms 142668 KB Output is correct
42 Correct 1515 ms 125964 KB Output is correct
43 Correct 1134 ms 125032 KB Output is correct
44 Correct 752 ms 123864 KB Output is correct
45 Correct 1926 ms 126924 KB Output is correct
46 Correct 1188 ms 124372 KB Output is correct
47 Correct 1575 ms 141456 KB Output is correct
48 Correct 1774 ms 139784 KB Output is correct
49 Correct 1780 ms 139896 KB Output is correct
50 Correct 1865 ms 141884 KB Output is correct
51 Correct 1716 ms 138984 KB Output is correct
52 Execution timed out 2016 ms 141532 KB Time limit exceeded
53 Halted 0 ms 0 KB -

Subtask #5
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 261 ms 118972 KB Output is correct
2 Correct 269 ms 119112 KB Output is correct
3 Correct 329 ms 119004 KB Output is correct
4 Correct 234 ms 118884 KB Output is correct
5 Correct 270 ms 119048 KB Output is correct
6 Correct 333 ms 119188 KB Output is correct
7 Correct 246 ms 119652 KB Output is correct
8 Correct 243 ms 120180 KB Output is correct
9 Correct 219 ms 120260 KB Output is correct
10 Correct 173 ms 120276 KB Output is correct
11 Correct 196 ms 120288 KB Output is correct
12 Correct 173 ms 120332 KB Output is correct
13 Correct 213 ms 120104 KB Output is correct
14 Correct 336 ms 119860 KB Output is correct
15 Correct 188 ms 120168 KB Output is correct
16 Correct 174 ms 120152 KB Output is correct
17 Correct 217 ms 120536 KB Output is correct
18 Correct 175 ms 119912 KB Output is correct
19 Correct 194 ms 120128 KB Output is correct
20 Correct 271 ms 120252 KB Output is correct
21 Correct 245 ms 120200 KB Output is correct
22 Correct 233 ms 120288 KB Output is correct
23 Correct 228 ms 120276 KB Output is correct
24 Correct 280 ms 120108 KB Output is correct
25 Correct 312 ms 120084 KB Output is correct
26 Correct 183 ms 120160 KB Output is correct
27 Correct 185 ms 119140 KB Output is correct
28 Correct 224 ms 120164 KB Output is correct
29 Correct 221 ms 120812 KB Output is correct
30 Correct 263 ms 121472 KB Output is correct
31 Correct 330 ms 121056 KB Output is correct
32 Correct 318 ms 120616 KB Output is correct
33 Correct 284 ms 121180 KB Output is correct
34 Correct 234 ms 121780 KB Output is correct
35 Correct 317 ms 122124 KB Output is correct
36 Correct 259 ms 121404 KB Output is correct
37 Correct 267 ms 122704 KB Output is correct
38 Correct 231 ms 121644 KB Output is correct
39 Correct 268 ms 120940 KB Output is correct
40 Correct 233 ms 120612 KB Output is correct
41 Correct 250 ms 121512 KB Output is correct
42 Correct 443 ms 121316 KB Output is correct
43 Correct 404 ms 121564 KB Output is correct
44 Correct 432 ms 121068 KB Output is correct
45 Correct 245 ms 121644 KB Output is correct
46 Correct 342 ms 121356 KB Output is correct
47 Correct 467 ms 121456 KB Output is correct
48 Correct 274 ms 121712 KB Output is correct
49 Correct 339 ms 121556 KB Output is correct
50 Correct 281 ms 122164 KB Output is correct
51 Correct 336 ms 121308 KB Output is correct
52 Correct 339 ms 121148 KB Output is correct
53 Correct 317 ms 121588 KB Output is correct
54 Correct 298 ms 122108 KB Output is correct
55 Correct 1145 ms 123956 KB Output is correct
56 Correct 443 ms 121808 KB Output is correct
57 Correct 1036 ms 123176 KB Output is correct
58 Correct 1326 ms 137880 KB Output is correct
59 Correct 1669 ms 139272 KB Output is correct
60 Correct 1166 ms 124040 KB Output is correct
61 Correct 983 ms 124696 KB Output is correct
62 Correct 1156 ms 123812 KB Output is correct
63 Correct 1175 ms 138448 KB Output is correct
64 Correct 1557 ms 139080 KB Output is correct
65 Correct 1176 ms 124140 KB Output is correct

Subtask #6
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 261 ms 118972 KB Output is correct
2 Correct 269 ms 119112 KB Output is correct
3 Correct 329 ms 119004 KB Output is correct
4 Correct 234 ms 118884 KB Output is correct
5 Correct 270 ms 119048 KB Output is correct
6 Correct 333 ms 119188 KB Output is correct
7 Correct 246 ms 119652 KB Output is correct
8 Correct 243 ms 120180 KB Output is correct
9 Correct 219 ms 120260 KB Output is correct
10 Correct 173 ms 120276 KB Output is correct
11 Correct 196 ms 120288 KB Output is correct
12 Correct 173 ms 120332 KB Output is correct
13 Correct 213 ms 120104 KB Output is correct
14 Correct 336 ms 119860 KB Output is correct
15 Correct 188 ms 120168 KB Output is correct
16 Correct 174 ms 120152 KB Output is correct
17 Correct 217 ms 120536 KB Output is correct
18 Correct 175 ms 119912 KB Output is correct
19 Correct 194 ms 120128 KB Output is correct
20 Correct 271 ms 120252 KB Output is correct
21 Correct 245 ms 120200 KB Output is correct
22 Correct 233 ms 120288 KB Output is correct
23 Correct 228 ms 120276 KB Output is correct
24 Correct 280 ms 120108 KB Output is correct
25 Correct 312 ms 120084 KB Output is correct
26 Correct 183 ms 120160 KB Output is correct
27 Correct 185 ms 119140 KB Output is correct
28 Correct 224 ms 120164 KB Output is correct
29 Correct 221 ms 120812 KB Output is correct
30 Correct 263 ms 121472 KB Output is correct
31 Correct 330 ms 121056 KB Output is correct
32 Correct 318 ms 120616 KB Output is correct
33 Correct 284 ms 121180 KB Output is correct
34 Correct 234 ms 121780 KB Output is correct
35 Correct 317 ms 122124 KB Output is correct
36 Correct 259 ms 121404 KB Output is correct
37 Correct 267 ms 122704 KB Output is correct
38 Correct 231 ms 121644 KB Output is correct
39 Correct 268 ms 120940 KB Output is correct
40 Correct 233 ms 120612 KB Output is correct
41 Correct 250 ms 121512 KB Output is correct
42 Correct 443 ms 121316 KB Output is correct
43 Correct 404 ms 121564 KB Output is correct
44 Correct 432 ms 121068 KB Output is correct
45 Correct 245 ms 121644 KB Output is correct
46 Correct 342 ms 121356 KB Output is correct
47 Correct 467 ms 121456 KB Output is correct
48 Correct 274 ms 121712 KB Output is correct
49 Correct 339 ms 121556 KB Output is correct
50 Correct 281 ms 122164 KB Output is correct
51 Correct 336 ms 121308 KB Output is correct
52 Correct 339 ms 121148 KB Output is correct
53 Correct 317 ms 121588 KB Output is correct
54 Correct 298 ms 122108 KB Output is correct
55 Correct 1707 ms 140060 KB Output is correct
56 Correct 596 ms 123984 KB Output is correct
57 Correct 1014 ms 124088 KB Output is correct
58 Correct 1423 ms 137788 KB Output is correct
59 Correct 1319 ms 141552 KB Output is correct
60 Correct 1487 ms 142764 KB Output is correct
61 Correct 1494 ms 142904 KB Output is correct
62 Correct 1197 ms 123740 KB Output is correct
63 Correct 1996 ms 141968 KB Output is correct
64 Correct 1268 ms 124228 KB Output is correct
65 Correct 1269 ms 137964 KB Output is correct
66 Correct 1422 ms 142368 KB Output is correct
67 Correct 1855 ms 142668 KB Output is correct
68 Correct 1515 ms 125964 KB Output is correct
69 Correct 1134 ms 125032 KB Output is correct
70 Correct 752 ms 123864 KB Output is correct
71 Correct 1926 ms 126924 KB Output is correct
72 Correct 1188 ms 124372 KB Output is correct
73 Correct 1575 ms 141456 KB Output is correct
74 Correct 1774 ms 139784 KB Output is correct
75 Correct 1780 ms 139896 KB Output is correct
76 Correct 1865 ms 141884 KB Output is correct
77 Correct 1716 ms 138984 KB Output is correct
78 Execution timed out 2016 ms 141532 KB Time limit exceeded
79 Halted 0 ms 0 KB -