oj.uz

Submission #306357

# Submission time Handle Problem Language Result Execution time Memory
306357 2020-09-25T09:41:17 Z llaki Stations (IOI20_stations) Java 11
57.3244 / 100
 1593 ms 42448 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;
        }
        int maxSize = 0;
        for (int i = 0; i < n; i++) {
            maxSize = Math.max(maxSize, G[i].size());
        }
        if (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 1153 ms 35752 KB Output is correct
2 Correct 1177 ms 38972 KB Output is correct
3 Correct 1453 ms 36596 KB Output is correct
4 Correct 1208 ms 34096 KB Output is correct
5 Correct 1199 ms 33476 KB Output is correct
6 Correct 1117 ms 38556 KB Output is correct
7 Correct 1076 ms 34612 KB Output is correct
8 Correct 174 ms 20816 KB Output is correct
9 Correct 181 ms 21076 KB Output is correct
10 Correct 167 ms 20928 KB Output is correct

Subtask #2
0 / 8.0

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

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 1330 ms 36620 KB Output is correct
2 Correct 1105 ms 38896 KB Output is correct
3 Correct 1593 ms 37972 KB Output is correct
4 Correct 1392 ms 35984 KB Output is correct
5 Correct 1070 ms 35104 KB Output is correct
6 Correct 1085 ms 36964 KB Output is correct
7 Correct 1126 ms 35148 KB Output is correct
8 Correct 167 ms 21016 KB Output is correct
9 Correct 182 ms 20920 KB Output is correct
10 Correct 167 ms 21160 KB Output is correct
11 Correct 1165 ms 34968 KB Output is correct
12 Correct 1158 ms 37104 KB Output is correct
13 Correct 1244 ms 40036 KB Output is correct
14 Correct 1035 ms 33596 KB Output is correct
15 Correct 327 ms 25428 KB Output is correct
16 Correct 437 ms 27980 KB Output is correct
17 Correct 651 ms 33596 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1410 ms 38548 KB Output is correct
2 Correct 1241 ms 34720 KB Output is correct
3 Correct 1345 ms 34080 KB Output is correct
4 Correct 165 ms 21012 KB Output is correct
5 Correct 177 ms 21272 KB Output is correct
6 Correct 160 ms 21232 KB Output is correct
7 Correct 1129 ms 34500 KB Output is correct
8 Correct 1479 ms 38640 KB Output is correct
9 Correct 1263 ms 35572 KB Output is correct
10 Correct 1251 ms 34512 KB Output is correct
11 Correct 188 ms 21584 KB Output is correct
12 Correct 196 ms 21484 KB Output is correct
13 Correct 182 ms 21044 KB Output is correct
14 Correct 178 ms 21212 KB Output is correct
15 Correct 168 ms 20772 KB Output is correct
16 Correct 1130 ms 33236 KB Output is correct
17 Correct 1128 ms 32984 KB Output is correct
18 Correct 1121 ms 34600 KB Output is correct
19 Correct 1161 ms 35756 KB Output is correct
20 Correct 1127 ms 34204 KB Output is correct

Subtask #5
26.3244 / 61.0

# Verdict Execution time Memory Grader output
1 Partially correct 1274 ms 38360 KB Partially correct
2 Partially correct 1029 ms 38636 KB Partially correct
3 Correct 1421 ms 36352 KB Output is correct
4 Partially correct 1290 ms 34644 KB Partially correct
5 Partially correct 1184 ms 33680 KB Partially correct
6 Partially correct 1131 ms 39260 KB Partially correct
7 Partially correct 1093 ms 35552 KB Partially correct
8 Partially correct 173 ms 21368 KB Partially correct
9 Correct 184 ms 20840 KB Output is correct
10 Partially correct 163 ms 20800 KB Partially correct
11 Partially correct 1124 ms 40016 KB Partially correct
12 Partially correct 1161 ms 37240 KB Partially correct
13 Correct 1492 ms 38832 KB Output is correct
14 Partially correct 1179 ms 35232 KB Partially correct
15 Partially correct 1127 ms 34616 KB Partially correct
16 Partially correct 1103 ms 35944 KB Partially correct
17 Partially correct 1127 ms 35744 KB Partially correct
18 Partially correct 1170 ms 38016 KB Partially correct
19 Partially correct 1190 ms 39960 KB Partially correct
20 Partially correct 1093 ms 33920 KB Partially correct
21 Partially correct 310 ms 25104 KB Partially correct
22 Partially correct 406 ms 27564 KB Partially correct
23 Partially correct 710 ms 36700 KB Partially correct
24 Partially correct 200 ms 21544 KB Partially correct
25 Partially correct 189 ms 21320 KB Partially correct
26 Partially correct 179 ms 20924 KB Partially correct
27 Partially correct 176 ms 20716 KB Partially correct
28 Partially correct 166 ms 21076 KB Partially correct
29 Partially correct 960 ms 33052 KB Partially correct
30 Partially correct 1161 ms 34332 KB Partially correct
31 Partially correct 1126 ms 33576 KB Partially correct
32 Partially correct 1147 ms 34224 KB Partially correct
33 Partially correct 1105 ms 34304 KB Partially correct
34 Partially correct 905 ms 37256 KB Partially correct
35 Partially correct 1007 ms 36220 KB Partially correct
36 Partially correct 1072 ms 39956 KB Partially correct
37 Partially correct 1150 ms 36052 KB Partially correct
38 Partially correct 1141 ms 41112 KB Partially correct
39 Partially correct 1141 ms 40800 KB Partially correct
40 Partially correct 1169 ms 42448 KB Partially correct
41 Partially correct 1064 ms 40188 KB Partially correct
42 Partially correct 454 ms 30668 KB Partially correct
43 Partially correct 665 ms 34784 KB Partially correct
44 Partially correct 697 ms 37000 KB Partially correct
45 Partially correct 803 ms 36876 KB Partially correct
46 Partially correct 956 ms 35184 KB Partially correct
47 Partially correct 933 ms 35604 KB Partially correct
48 Partially correct 411 ms 30976 KB Partially correct
49 Partially correct 415 ms 29376 KB Partially correct