oj.uz

Submission #306366

# Submission time Handle Problem Language Result Execution time Memory
306366 2020-09-25T09:59:59 Z llaki Stations (IOI20_stations) Java 11
57.3244 / 100
 1809 ms 41776 KB 
import java.util.ArrayList;

public class stations {
    void dfsLabel(int v, int p, ArrayList<Integer>[] G, int[] labels) {
        int min = label;
        for (int to : G[v]) {
            if (p != to) {
                dfsLabel(to, v, G, labels);
            }
        }
        int max = label;
        labels[v] = 1000 * min + max;
        label++;
    }

    int label = 0;

    int[] label(int n, int k, int[] u, int[] v) {
        ArrayList<Integer>[] G = new ArrayList[n];
        for (int i = 0; i < G.length; i++) {
            G[i] = new ArrayList<>();
        }
        for (int i = 0; i < u.length; i++) {
            G[u[i]].add(v[i]);
            G[v[i]].add(u[i]);
        }
        int[] labels = new int[n];
        if (k > 1000) {
            label = 0;
            dfsLabel(0, 0, G, labels);
            return labels;
        }
        boolean allTask2 = true;
        for (int i = 0; i < n - 1; i++) {
            if (u[i] == i + 1 && v[i] == i / 2) {
                continue;
            }
            if (v[i] == i + 1 && u[i] == i / 2) {
                continue;
            }
            allTask2 = false;
            break;
        }
        int maxSize = 0;
        for (int i = 0; i < n; i++) {
            maxSize = Math.max(maxSize, G[i].size());
        }
        if (allTask2 && maxSize > 2) {
            for (int i = 0; i < n; i++) {
                labels[i] = i;
            }
            return labels;
        }
        int leaf = -1;
        for (int i = 0; i < n; i++) {
            if (G[i].size() == 1) {
                leaf = i;
                break;
            }
        }
        int cur = 0;
        int node = leaf;
        int prev = -1;
        while (true) {
            labels[node] = cur;
            cur++;
            boolean found = false;
            for (int to : G[node]) {
                if (to == prev) continue;
                prev = node;
                node = to;
                found = true;
                break;
            }
            if (!found) break;
        }
        return labels;
    }

    boolean isAncestor(int a, int b) {
        if (a == b) return true;
        while (a > 0) {
            a = (a - 1) / 2;
            if (a == b) return true;
        }
        return false;
    }

    int find_next_station(int s, int t, int[] c) {
        boolean isLarge = true;
        if (s >= 1000 || t >= 1000) isLarge = true;
        for (int nd : c) if (nd >= 1000) isLarge = true;
        if (isLarge) {
            int dest = t % 1000;
            for (int nd : c) {
                if (nd % 1000 > s % 1000) continue;
                int min = nd / 1000, max = nd % 1000;
                if (min <= dest && dest <= max) {
                    return nd;
                }
            }
            for (int nd : c) {
                if (nd % 1000 > s % 1000) return nd;
            }
        }
        boolean isBamboo = true;
        if (c.length > 2) {
            isBamboo = false;
        }
        else {
            for (int nd : c) {
                if (Math.abs(nd - s) > 1) isBamboo = false;
            }
        }
        if (!isBamboo) {
            if (!isAncestor(t, s)) {
                return (s - 1) / 2;
            }
            for (int nd : c) {
                if (nd < s) continue;
                if (isAncestor(t, nd)) {
                    return nd;
                }
            }
        } else {
            for (int nd : c) {
                if (s <= nd && nd <= t) return nd;
                if (s >= nd && nd >= t) return nd;
            }
        }
        return -1;
    }
}

Compilation message

Note: stations.java uses unchecked or unsafe operations.
Note: Recompile with -Xlint:unchecked for details.

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1295 ms 35960 KB Output is correct
2 Correct 1115 ms 38296 KB Output is correct
3 Correct 1809 ms 36612 KB Output is correct
4 Correct 1345 ms 36376 KB Output is correct
5 Correct 1318 ms 35108 KB Output is correct
6 Correct 1299 ms 38568 KB Output is correct
7 Correct 1156 ms 33000 KB Output is correct
8 Correct 187 ms 21132 KB Output is correct
9 Correct 193 ms 21120 KB Output is correct
10 Correct 175 ms 21016 KB Output is correct

Subtask #2
0 / 8.0

# Verdict Execution time Memory Grader output
1 Incorrect 1197 ms 37372 KB Wrong query response.
2 Halted 0 ms 0 KB -

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 1221 ms 37248 KB Output is correct
2 Correct 1144 ms 36396 KB Output is correct
3 Correct 1575 ms 37904 KB Output is correct
4 Correct 1385 ms 35204 KB Output is correct
5 Correct 1200 ms 36860 KB Output is correct
6 Correct 1165 ms 39436 KB Output is correct
7 Correct 1036 ms 35136 KB Output is correct
8 Correct 169 ms 20488 KB Output is correct
9 Correct 186 ms 21220 KB Output is correct
10 Correct 166 ms 20852 KB Output is correct
11 Correct 1155 ms 35904 KB Output is correct
12 Correct 1204 ms 37932 KB Output is correct
13 Correct 1300 ms 39640 KB Output is correct
14 Correct 1177 ms 33064 KB Output is correct
15 Correct 348 ms 25508 KB Output is correct
16 Correct 467 ms 28212 KB Output is correct
17 Correct 655 ms 35664 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1531 ms 35780 KB Output is correct
2 Correct 1310 ms 36440 KB Output is correct
3 Correct 1184 ms 34480 KB Output is correct
4 Correct 178 ms 20832 KB Output is correct
5 Correct 184 ms 21156 KB Output is correct
6 Correct 165 ms 20616 KB Output is correct
7 Correct 1222 ms 33896 KB Output is correct
8 Correct 1563 ms 38404 KB Output is correct
9 Correct 1290 ms 36404 KB Output is correct
10 Correct 1188 ms 35680 KB Output is correct
11 Correct 203 ms 21432 KB Output is correct
12 Correct 193 ms 21204 KB Output is correct
13 Correct 181 ms 21104 KB Output is correct
14 Correct 181 ms 21056 KB Output is correct
15 Correct 164 ms 21004 KB Output is correct
16 Correct 1247 ms 34828 KB Output is correct
17 Correct 1044 ms 34952 KB Output is correct
18 Correct 1202 ms 33440 KB Output is correct
19 Correct 1060 ms 33364 KB Output is correct
20 Correct 929 ms 34852 KB Output is correct

Subtask #5
26.3244 / 61.0

# Verdict Execution time Memory Grader output
1 Partially correct 1172 ms 36524 KB Partially correct
2 Partially correct 1133 ms 37376 KB Partially correct
3 Correct 1609 ms 39560 KB Output is correct
4 Partially correct 1283 ms 35608 KB Partially correct
5 Partially correct 1206 ms 35840 KB Partially correct
6 Partially correct 1124 ms 37504 KB Partially correct
7 Partially correct 1093 ms 33500 KB Partially correct
8 Partially correct 168 ms 20840 KB Partially correct
9 Correct 181 ms 21020 KB Output is correct
10 Partially correct 164 ms 21032 KB Partially correct
11 Partially correct 1196 ms 38752 KB Partially correct
12 Partially correct 1190 ms 36888 KB Partially correct
13 Correct 1465 ms 38476 KB Output is correct
14 Partially correct 1295 ms 35476 KB Partially correct
15 Partially correct 1186 ms 35964 KB Partially correct
16 Partially correct 1110 ms 33800 KB Partially correct
17 Partially correct 1271 ms 36576 KB Partially correct
18 Partially correct 1191 ms 37608 KB Partially correct
19 Partially correct 1260 ms 41608 KB Partially correct
20 Partially correct 1032 ms 35388 KB Partially correct
21 Partially correct 363 ms 25256 KB Partially correct
22 Partially correct 479 ms 26684 KB Partially correct
23 Partially correct 630 ms 34280 KB Partially correct
24 Partially correct 190 ms 21400 KB Partially correct
25 Partially correct 189 ms 21208 KB Partially correct
26 Partially correct 188 ms 20888 KB Partially correct
27 Partially correct 175 ms 21004 KB Partially correct
28 Partially correct 163 ms 20996 KB Partially correct
29 Partially correct 1235 ms 32984 KB Partially correct
30 Partially correct 1093 ms 33612 KB Partially correct
31 Partially correct 1107 ms 35552 KB Partially correct
32 Partially correct 1081 ms 33932 KB Partially correct
33 Partially correct 1200 ms 33352 KB Partially correct
34 Partially correct 929 ms 35500 KB Partially correct
35 Partially correct 1121 ms 36004 KB Partially correct
36 Partially correct 1168 ms 38420 KB Partially correct
37 Partially correct 1266 ms 39728 KB Partially correct
38 Partially correct 1149 ms 38632 KB Partially correct
39 Partially correct 1156 ms 41016 KB Partially correct
40 Partially correct 1134 ms 39492 KB Partially correct
41 Partially correct 1200 ms 41776 KB Partially correct
42 Partially correct 455 ms 30152 KB Partially correct
43 Partially correct 656 ms 34240 KB Partially correct
44 Partially correct 689 ms 35632 KB Partially correct
45 Partially correct 776 ms 35388 KB Partially correct
46 Partially correct 881 ms 33768 KB Partially correct
47 Partially correct 937 ms 36856 KB Partially correct
48 Partially correct 477 ms 31780 KB Partially correct
49 Partially correct 441 ms 32960 KB Partially correct