oj.uz

Submission #306354

# Submission time Handle Problem Language Result Execution time Memory
306354 2020-09-25T09:29:37 Z llaki Stations (IOI20_stations) Java 11
13 / 100
 1724 ms 39136 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 % 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 1347 ms 36308 KB Output is correct
2 Correct 1152 ms 38612 KB Output is correct
3 Correct 1398 ms 38332 KB Output is correct
4 Correct 1210 ms 33924 KB Output is correct
5 Correct 1398 ms 35592 KB Output is correct
6 Correct 1209 ms 38212 KB Output is correct
7 Correct 1175 ms 34732 KB Output is correct
8 Correct 175 ms 20976 KB Output is correct
9 Correct 185 ms 21256 KB Output is correct
10 Correct 160 ms 20712 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1057 ms 37564 KB Output is correct
2 Correct 1304 ms 36312 KB Output is correct
3 Correct 1531 ms 37264 KB Output is correct
4 Correct 1459 ms 33904 KB Output is correct
5 Correct 1244 ms 35976 KB Output is correct
6 Correct 1039 ms 33880 KB Output is correct

Subtask #3
0 / 16.0

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

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1684 ms 37792 KB Output is correct
2 Correct 1395 ms 36580 KB Output is correct
3 Correct 1209 ms 34980 KB Output is correct
4 Correct 180 ms 20776 KB Output is correct
5 Correct 187 ms 21260 KB Output is correct
6 Correct 166 ms 20884 KB Output is correct
7 Incorrect 1180 ms 35708 KB Wrong query response.
8 Halted 0 ms 0 KB -

Subtask #5
0 / 61.0

# Verdict Execution time Memory Grader output
1 Correct 1157 ms 37464 KB Output is correct
2 Correct 1144 ms 39136 KB Output is correct
3 Correct 1548 ms 36976 KB Output is correct
4 Correct 1266 ms 34212 KB Output is correct
5 Correct 1139 ms 34000 KB Output is correct
6 Correct 1126 ms 38140 KB Output is correct
7 Correct 1065 ms 32636 KB Output is correct
8 Correct 165 ms 21196 KB Output is correct
9 Correct 187 ms 21444 KB Output is correct
10 Correct 166 ms 21188 KB Output is correct
11 Correct 1138 ms 38372 KB Output is correct
12 Correct 1104 ms 35572 KB Output is correct
13 Correct 1724 ms 38428 KB Output is correct
14 Correct 1210 ms 35864 KB Output is correct
15 Correct 1189 ms 33916 KB Output is correct
16 Correct 1083 ms 33016 KB Output is correct
17 Incorrect 1121 ms 35148 KB Wrong query response.
18 Halted 0 ms 0 KB -