oj.uz

Submission #306368

# Submission time Handle Problem Language Result Execution time Memory
306368 2020-09-25T10:07:57 Z llaki Stations (IOI20_stations) Java 11
5 / 100
 1608 ms 40536 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 = false;
        if (s >= 1000 || t >= 1000) isLarge = true;
        for (int nd : c) if (nd >= 1000) isLarge = true;
        boolean isTask2 = true;
        for (int nd : c) {
            if (nd != s / 2 && nd != 2 * s + 1 && nd != 2 * s + 2) isTask2 = false;
        }
        if (isLarge || !isTask2) {
            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 1220 ms 37420 KB Output is correct
2 Correct 1172 ms 39748 KB Output is correct
3 Correct 1608 ms 36204 KB Output is correct
4 Correct 1223 ms 34208 KB Output is correct
5 Correct 1357 ms 33288 KB Output is correct
6 Correct 1219 ms 38924 KB Output is correct
7 Correct 1171 ms 34104 KB Output is correct
8 Correct 174 ms 20808 KB Output is correct
9 Correct 185 ms 21268 KB Output is correct
10 Correct 168 ms 20776 KB Output is correct

Subtask #2
0 / 8.0

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

Subtask #3
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 1126 ms 36824 KB Output is correct
2 Correct 1115 ms 39840 KB Output is correct
3 Correct 1556 ms 36828 KB Output is correct
4 Correct 1376 ms 35988 KB Output is correct
5 Correct 1156 ms 35508 KB Output is correct
6 Correct 1262 ms 38648 KB Output is correct
7 Correct 1158 ms 34788 KB Output is correct
8 Correct 172 ms 21268 KB Output is correct
9 Correct 184 ms 21060 KB Output is correct
10 Correct 164 ms 21048 KB Output is correct
11 Incorrect 1232 ms 36624 KB Wrong query response.
12 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1551 ms 37528 KB Output is correct
2 Correct 1280 ms 34996 KB Output is correct
3 Correct 1258 ms 34748 KB Output is correct
4 Correct 170 ms 21148 KB Output is correct
5 Correct 189 ms 21056 KB Output is correct
6 Correct 164 ms 21440 KB Output is correct
7 Incorrect 1379 ms 35804 KB Wrong query response.
8 Halted 0 ms 0 KB -

Subtask #5
0 / 61.0

# Verdict Execution time Memory Grader output
1 Partially correct 1194 ms 37752 KB Partially correct
2 Partially correct 1113 ms 36492 KB Partially correct
3 Correct 1522 ms 36944 KB Output is correct
4 Partially correct 1253 ms 32900 KB Partially correct
5 Partially correct 1239 ms 35092 KB Partially correct
6 Partially correct 1072 ms 40136 KB Partially correct
7 Partially correct 1068 ms 33484 KB Partially correct
8 Partially correct 169 ms 21156 KB Partially correct
9 Correct 183 ms 21428 KB Output is correct
10 Partially correct 166 ms 21084 KB Partially correct
11 Partially correct 1183 ms 40536 KB Partially correct
12 Partially correct 1155 ms 34140 KB Partially correct
13 Correct 1577 ms 36732 KB Output is correct
14 Partially correct 1347 ms 36108 KB Partially correct
15 Partially correct 1240 ms 35248 KB Partially correct
16 Partially correct 1083 ms 34964 KB Partially correct
17 Incorrect 1345 ms 35416 KB Wrong query response.
18 Halted 0 ms 0 KB -