oj.uz

Submission #306355

# Submission time Handle Problem Language Result Execution time Memory
306355 2020-09-25T09:32:43 Z llaki Stations (IOI20_stations) Java 11
21 / 100
 1799 ms 40032 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 == 1000000) {
            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) {
            for (int nd : c) {
                if (nd % 1000 > s % 1000) continue;
                int min = nd / 1000, max = nd % 1000;
                int dest = t % 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 1137 ms 34856 KB Output is correct
2 Correct 1196 ms 37564 KB Output is correct
3 Correct 1799 ms 38440 KB Output is correct
4 Correct 1309 ms 34436 KB Output is correct
5 Correct 1197 ms 33428 KB Output is correct
6 Correct 1202 ms 38828 KB Output is correct
7 Correct 1102 ms 34436 KB Output is correct
8 Correct 166 ms 21108 KB Output is correct
9 Correct 188 ms 21404 KB Output is correct
10 Correct 162 ms 21116 KB Output is correct

Subtask #2
0 / 8.0

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

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 1263 ms 36560 KB Output is correct
2 Correct 1086 ms 37208 KB Output is correct
3 Correct 1633 ms 38136 KB Output is correct
4 Correct 1316 ms 35392 KB Output is correct
5 Correct 1247 ms 33952 KB Output is correct
6 Correct 1167 ms 38284 KB Output is correct
7 Correct 1101 ms 33520 KB Output is correct
8 Correct 165 ms 20912 KB Output is correct
9 Correct 181 ms 21232 KB Output is correct
10 Correct 166 ms 21368 KB Output is correct
11 Correct 1258 ms 35484 KB Output is correct
12 Correct 1147 ms 39224 KB Output is correct
13 Correct 1148 ms 40032 KB Output is correct
14 Correct 1143 ms 33188 KB Output is correct
15 Correct 343 ms 25656 KB Output is correct
16 Correct 405 ms 29048 KB Output is correct
17 Correct 670 ms 33856 KB Output is correct

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1618 ms 38492 KB Output is correct
2 Correct 1250 ms 35964 KB Output is correct
3 Correct 1105 ms 32620 KB Output is correct
4 Correct 172 ms 20792 KB Output is correct
5 Correct 187 ms 20924 KB Output is correct
6 Correct 160 ms 20684 KB Output is correct
7 Incorrect 1314 ms 35028 KB Wrong query response.
8 Halted 0 ms 0 KB -

Subtask #5
0 / 61.0

# Verdict Execution time Memory Grader output
1 Correct 1154 ms 34876 KB Output is correct
2 Correct 1146 ms 38124 KB Output is correct
3 Correct 1402 ms 38336 KB Output is correct
4 Correct 1247 ms 34632 KB Output is correct
5 Correct 1128 ms 35196 KB Output is correct
6 Correct 1025 ms 38220 KB Output is correct
7 Correct 1026 ms 34760 KB Output is correct
8 Correct 167 ms 20988 KB Output is correct
9 Correct 173 ms 21244 KB Output is correct
10 Correct 154 ms 20884 KB Output is correct
11 Incorrect 1105 ms 36268 KB Wrong query response.
12 Halted 0 ms 0 KB -