oj.uz

Submission #306015

# Submission time Handle Problem Language Result Execution time Memory
306015 2020-09-24T09:44:29 Z llaki Stations (IOI20_stations) Java 11
13 / 100
 1707 ms 40016 KB 
import java.util.ArrayList;

public class stations {

    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 maxSize = 0;
        for (int i = 0; i < n; i++) {
            maxSize = Math.max(maxSize, G[i].size());
        }
        int[] labels = new int[n];
        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 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 1130 ms 36812 KB Output is correct
2 Correct 1084 ms 38512 KB Output is correct
3 Correct 1556 ms 38036 KB Output is correct
4 Correct 1320 ms 36368 KB Output is correct
5 Correct 1169 ms 35916 KB Output is correct
6 Correct 1301 ms 39752 KB Output is correct
7 Correct 1109 ms 32900 KB Output is correct
8 Correct 175 ms 21196 KB Output is correct
9 Correct 183 ms 21064 KB Output is correct
10 Correct 163 ms 20916 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1216 ms 36928 KB Output is correct
2 Correct 1214 ms 34816 KB Output is correct
3 Correct 1379 ms 38956 KB Output is correct
4 Correct 1272 ms 37040 KB Output is correct
5 Correct 1227 ms 32972 KB Output is correct
6 Correct 1010 ms 32452 KB Output is correct

Subtask #3
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 1198 ms 37596 KB Output is correct
2 Correct 1087 ms 37200 KB Output is correct
3 Correct 1402 ms 40016 KB Output is correct
4 Correct 1237 ms 33140 KB Output is correct
5 Correct 1156 ms 33660 KB Output is correct
6 Correct 1153 ms 37620 KB Output is correct
7 Correct 1140 ms 33300 KB Output is correct
8 Correct 179 ms 21060 KB Output is correct
9 Correct 185 ms 20932 KB Output is correct
10 Correct 164 ms 20732 KB Output is correct
11 Incorrect 1291 ms 33392 KB Wrong query response.
12 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1463 ms 36976 KB Output is correct
2 Correct 1288 ms 34916 KB Output is correct
3 Correct 1196 ms 35008 KB Output is correct
4 Correct 168 ms 20948 KB Output is correct
5 Correct 183 ms 21204 KB Output is correct
6 Correct 178 ms 20944 KB Output is correct
7 Incorrect 1238 ms 33716 KB Wrong query response.
8 Halted 0 ms 0 KB -

Subtask #5
0 / 61.0

# Verdict Execution time Memory Grader output
1 Correct 1287 ms 36088 KB Output is correct
2 Correct 1223 ms 36316 KB Output is correct
3 Correct 1541 ms 37352 KB Output is correct
4 Correct 1299 ms 34504 KB Output is correct
5 Correct 1063 ms 33960 KB Output is correct
6 Correct 1082 ms 38340 KB Output is correct
7 Correct 989 ms 32492 KB Output is correct
8 Correct 169 ms 20956 KB Output is correct
9 Correct 181 ms 20888 KB Output is correct
10 Correct 166 ms 20884 KB Output is correct
11 Correct 1151 ms 36504 KB Output is correct
12 Correct 1283 ms 35524 KB Output is correct
13 Correct 1707 ms 39296 KB Output is correct
14 Correct 1266 ms 36632 KB Output is correct
15 Correct 1278 ms 34508 KB Output is correct
16 Correct 1034 ms 31968 KB Output is correct
17 Incorrect 1119 ms 35496 KB Wrong query response.
18 Halted 0 ms 0 KB -