oj.uz

Submission #306351

# Submission time Handle Problem Language Result Execution time Memory
306351 2020-09-25T09:27:40 Z llaki Stations (IOI20_stations) Java 11
13 / 100
 1706 ms 38884 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 = false;
        if (s >= 1000 || t >= 1000) isLarge = true;
        for (int nd : c) if (nd >= 1000) isLarge = true;
        if (isLarge) {
            for (int nd : c) {
                if (nd > 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 > 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 1238 ms 36644 KB Output is correct
2 Correct 1090 ms 38272 KB Output is correct
3 Correct 1452 ms 36460 KB Output is correct
4 Correct 1155 ms 35440 KB Output is correct
5 Correct 1154 ms 33836 KB Output is correct
6 Correct 1169 ms 38244 KB Output is correct
7 Correct 1094 ms 34512 KB Output is correct
8 Correct 173 ms 20464 KB Output is correct
9 Correct 178 ms 21216 KB Output is correct
10 Correct 162 ms 20780 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1144 ms 38284 KB Output is correct
2 Correct 1189 ms 36092 KB Output is correct
3 Correct 1561 ms 38884 KB Output is correct
4 Correct 1320 ms 34384 KB Output is correct
5 Correct 1134 ms 34776 KB Output is correct
6 Correct 1016 ms 33416 KB Output is correct

Subtask #3
0 / 16.0

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

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1706 ms 38532 KB Output is correct
2 Correct 1286 ms 35668 KB Output is correct
3 Correct 1148 ms 34492 KB Output is correct
4 Correct 166 ms 21136 KB Output is correct
5 Correct 181 ms 21036 KB Output is correct
6 Correct 159 ms 21240 KB Output is correct
7 Incorrect 1210 ms 33784 KB Wrong query response.
8 Halted 0 ms 0 KB -

Subtask #5
0 / 61.0

# Verdict Execution time Memory Grader output
1 Correct 1089 ms 36704 KB Output is correct
2 Correct 1061 ms 35912 KB Output is correct
3 Correct 1435 ms 38076 KB Output is correct
4 Correct 1327 ms 35548 KB Output is correct
5 Correct 1230 ms 34572 KB Output is correct
6 Correct 1137 ms 36168 KB Output is correct
7 Correct 1173 ms 32304 KB Output is correct
8 Correct 174 ms 20852 KB Output is correct
9 Correct 186 ms 21164 KB Output is correct
10 Correct 172 ms 20920 KB Output is correct
11 Correct 1179 ms 36052 KB Output is correct
12 Correct 1185 ms 34584 KB Output is correct
13 Correct 1482 ms 38152 KB Output is correct
14 Correct 1354 ms 35192 KB Output is correct
15 Correct 1148 ms 34048 KB Output is correct
16 Correct 1107 ms 32576 KB Output is correct
17 Incorrect 1316 ms 35504 KB Wrong query response.
18 Halted 0 ms 0 KB -