oj.uz

Submission #304911

# Submission time Handle Problem Language Result Execution time Memory
304911 2020-09-22T07:42:12 Z model_code Stations (IOI20_stations) Java 11
100 / 100
 1722 ms 45532 KB 
import java.util.ArrayList;

public class stations {
  private static final int MAXN = 1000;
  
  private int cnt;
  private ArrayList<Integer>[] adj;
  private int[] labels;
  
  private void dfs(int v, int p, int d) {
  	if(d == 0) labels[v] = cnt++;
  	for (Integer i : adj[v]) if (i != p) dfs(i, v, d ^ 1);
  	if(d == 1) labels[v] = cnt++;
  }

  int[] label(int n, int k, int[] u, int[] v) {
    cnt = 0;
    adj = new ArrayList[n];
    for (int i = 0; i < n; i++) {
      adj[i] = new ArrayList<Integer>();
    }
  	for (int i = 0; i < n - 1; i++) {
  		adj[u[i]].add(v[i]);
  		adj[v[i]].add(u[i]);
  	}
  	labels = new int[n];
  	dfs(0, -1, 0);
  	return labels;
  }

  int find_next_station(int s, int t, int[] c) {
  	if (s < c[0]) {
  		if (t < s || t >= c[c.length - 1]) return c[c.length - 1];
  		for (int i : c) if (i >= t) return i;
    	return c[c.length - 1];
  	}
  	if (t > s || t <= c[0]) return c[0];
  	int ans = c[0];
  	for (int i : c) if (i <= t) ans = i;
  	return ans;
  }
}

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 1138 ms 39308 KB Output is correct
2 Correct 1276 ms 42364 KB Output is correct
3 Correct 1597 ms 43220 KB Output is correct
4 Correct 1278 ms 38860 KB Output is correct
5 Correct 1371 ms 41696 KB Output is correct
6 Correct 1297 ms 41156 KB Output is correct
7 Correct 1304 ms 38868 KB Output is correct
8 Correct 172 ms 23104 KB Output is correct
9 Correct 199 ms 22908 KB Output is correct
10 Correct 164 ms 23012 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1265 ms 45532 KB Output is correct
2 Correct 1268 ms 39748 KB Output is correct
3 Correct 1533 ms 40744 KB Output is correct
4 Correct 1529 ms 41132 KB Output is correct
5 Correct 1432 ms 38972 KB Output is correct
6 Correct 1229 ms 39004 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 1424 ms 40148 KB Output is correct
2 Correct 1299 ms 40708 KB Output is correct
3 Correct 1706 ms 43312 KB Output is correct
4 Correct 1397 ms 42656 KB Output is correct
5 Correct 1293 ms 38684 KB Output is correct
6 Correct 1263 ms 42260 KB Output is correct
7 Correct 1311 ms 39076 KB Output is correct
8 Correct 175 ms 22884 KB Output is correct
9 Correct 185 ms 23452 KB Output is correct
10 Correct 162 ms 23220 KB Output is correct
11 Correct 1331 ms 40680 KB Output is correct
12 Correct 1351 ms 42164 KB Output is correct
13 Correct 1299 ms 41548 KB Output is correct
14 Correct 1249 ms 38956 KB Output is correct
15 Correct 377 ms 27104 KB Output is correct
16 Correct 438 ms 29616 KB Output is correct
17 Correct 596 ms 34000 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1585 ms 43968 KB Output is correct
2 Correct 1308 ms 39080 KB Output is correct
3 Correct 1261 ms 39048 KB Output is correct
4 Correct 177 ms 23012 KB Output is correct
5 Correct 183 ms 23228 KB Output is correct
6 Correct 165 ms 22996 KB Output is correct
7 Correct 1417 ms 39936 KB Output is correct
8 Correct 1549 ms 42560 KB Output is correct
9 Correct 1404 ms 39484 KB Output is correct
10 Correct 1422 ms 40184 KB Output is correct
11 Correct 197 ms 23300 KB Output is correct
12 Correct 192 ms 23144 KB Output is correct
13 Correct 196 ms 23224 KB Output is correct
14 Correct 191 ms 22908 KB Output is correct
15 Correct 162 ms 22972 KB Output is correct
16 Correct 1196 ms 39844 KB Output is correct
17 Correct 1180 ms 38896 KB Output is correct
18 Correct 1275 ms 38068 KB Output is correct
19 Correct 1232 ms 39008 KB Output is correct
20 Correct 1181 ms 39720 KB Output is correct

Subtask #5
61.0 / 61.0

# Verdict Execution time Memory Grader output
1 Correct 1369 ms 40068 KB Output is correct
2 Correct 1273 ms 42380 KB Output is correct
3 Correct 1714 ms 42832 KB Output is correct
4 Correct 1476 ms 40396 KB Output is correct
5 Correct 1263 ms 38544 KB Output is correct
6 Correct 1124 ms 42576 KB Output is correct
7 Correct 1278 ms 39664 KB Output is correct
8 Correct 182 ms 23904 KB Output is correct
9 Correct 197 ms 23064 KB Output is correct
10 Correct 178 ms 22892 KB Output is correct
11 Correct 1298 ms 43400 KB Output is correct
12 Correct 1284 ms 39464 KB Output is correct
13 Correct 1722 ms 41764 KB Output is correct
14 Correct 1451 ms 40860 KB Output is correct
15 Correct 1183 ms 38996 KB Output is correct
16 Correct 1202 ms 39272 KB Output is correct
17 Correct 1288 ms 39760 KB Output is correct
18 Correct 1396 ms 41620 KB Output is correct
19 Correct 1254 ms 41964 KB Output is correct
20 Correct 1246 ms 39356 KB Output is correct
21 Correct 383 ms 26892 KB Output is correct
22 Correct 446 ms 28624 KB Output is correct
23 Correct 722 ms 36176 KB Output is correct
24 Correct 209 ms 23376 KB Output is correct
25 Correct 191 ms 23092 KB Output is correct
26 Correct 193 ms 23308 KB Output is correct
27 Correct 179 ms 23276 KB Output is correct
28 Correct 159 ms 23064 KB Output is correct
29 Correct 1079 ms 39720 KB Output is correct
30 Correct 1043 ms 38404 KB Output is correct
31 Correct 1311 ms 39460 KB Output is correct
32 Correct 1404 ms 40096 KB Output is correct
33 Correct 1210 ms 37048 KB Output is correct
34 Correct 1053 ms 35776 KB Output is correct
35 Correct 1247 ms 41484 KB Output is correct
36 Correct 1436 ms 42204 KB Output is correct
37 Correct 1298 ms 41288 KB Output is correct
38 Correct 1349 ms 44860 KB Output is correct
39 Correct 1188 ms 42112 KB Output is correct
40 Correct 1188 ms 40924 KB Output is correct
41 Correct 1279 ms 40780 KB Output is correct
42 Correct 384 ms 28828 KB Output is correct
43 Correct 607 ms 36892 KB Output is correct
44 Correct 716 ms 35944 KB Output is correct
45 Correct 850 ms 41188 KB Output is correct
46 Correct 1014 ms 37132 KB Output is correct
47 Correct 1093 ms 40236 KB Output is correct
48 Correct 482 ms 30824 KB Output is correct
49 Correct 433 ms 31284 KB Output is correct