Submission #617246
Source Code Expand
// package atcoder.dwango2016.qual; import java.io.IOException; import java.io.InputStream; import java.io.PrintWriter; import java.util.*; /** * Created by hama_du on 2016/01/23. */ public class Main { private static final long INF = (long) 1e18; public static void main(String[] args) { InputReader in = new InputReader(System.in); PrintWriter out = new PrintWriter(System.out); int n = in.nextInt(); int m = in.nextInt(); int start = in.nextInt(); int goal = in.nextInt(); List<Edge>[] graph = new List[n]; for (int i = 0; i < n ; i++) { graph[i] = new ArrayList<>(); } int[][] finish = new int[m][2]; int[][][] timeToFinish = new int[m][][]; for (int i = 0; i < m ; i++) { int l = in.nextInt(); int[] stations = new int[l]; int[] time = new int[l-1]; for (int j = 0; j < l ; j++) { stations[j] = in.nextInt(); } for (int j = 0; j < l-1 ; j++) { time[j] = in.nextInt(); } for (int j = 0; j < l-1 ; j++) { int a = stations[j]; int b = stations[j+1]; graph[a].add(new Edge(i, j, b, 1, time[j])); } for (int j = l-1 ; j >= 1 ; j--) { int a = stations[j]; int b = stations[j-1]; graph[a].add(new Edge(i, j, b, -1, time[j-1])); } finish[i][0] = stations[0]; finish[i][1] = stations[l-1]; timeToFinish[i] = new int[2][l]; // go for (int j = l-2 ; j >= 0 ; j--) { timeToFinish[i][0][j] = timeToFinish[i][0][j+1] + time[j]; } // rev for (int j = 1 ; j < l ; j++) { timeToFinish[i][1][j] = timeToFinish[i][1][j-1] + time[j-1]; } } long[] toGoal = new long[n]; Arrays.fill(toGoal, INF); toGoal[goal] = 0; Queue<State> q = new PriorityQueue<>(); q.add(new State(goal, 0L)); while (q.size() >= 1) { State st = q.poll(); int now = st.now; long time = st.time; if (toGoal[now] < time) { continue; } for (Edge e : graph[now]) { int to = e.to; long ttime = time + e.w; if (toGoal[to] > ttime) { toGoal[to] = ttime; q.add(new State(to, ttime)); } } } long max = INF/100000; long min = 0; while (max - min > 1) { long time = (max + min) / 2; if (isOK(time, toGoal, graph, finish, timeToFinish, start, goal)) { max = time; } else { min = time; } } out.println(max); out.flush(); } private static boolean isOK(long limit, long[] toGoal, List<Edge>[] graph, int[][] finish, int[][][] timeToFinish, int start, int goal) { int n = graph.length; long[] best = new long[n]; Arrays.fill(best, INF); best[start] = 0; Queue<State> q = new PriorityQueue<>(); q.add(new State(start, 0L)); while (q.size() >= 1) { State st = q.poll(); int now = st.now; long time = st.time; if (best[now] < time) { continue; } for (Edge e : graph[now]) { int to = e.to; long ttime = time + e.w; int expStation = finish[e.line][e.dir == 1 ? 1 : 0]; if (time + timeToFinish[e.line][e.dir == 1 ? 0 : 1][e.num] + toGoal[expStation] > limit) { continue; } if (best[to] > ttime) { best[to] = ttime; q.add(new State(to, ttime)); } } } return best[goal] <= limit; } static class State implements Comparable<State> { int now; long time; public State(int a, long b) { now = a; time = b; } @Override public int compareTo(State o) { return Long.compare(time, o.time); } } static class Edge { int line; int num; int to; int dir; int w; public Edge(int z, int n, int a, int b, int c) { line = z; num = n; to = a; dir = b; w = c; } } static class InputReader { private InputStream stream; private byte[] buf = new byte[1024]; private int curChar; private int numChars; public InputReader(InputStream stream) { this.stream = stream; } private int next() { if (numChars == -1) throw new InputMismatchException(); if (curChar >= numChars) { curChar = 0; try { numChars = stream.read(buf); } catch (IOException e) { throw new InputMismatchException(); } if (numChars <= 0) return -1; } return buf[curChar++]; } public char nextChar() { int c = next(); while (isSpaceChar(c)) c = next(); if ('a' <= c && c <= 'z') { return (char) c; } if ('A' <= c && c <= 'Z') { return (char) c; } throw new InputMismatchException(); } public String nextToken() { int c = next(); while (isSpaceChar(c)) c = next(); StringBuilder res = new StringBuilder(); do { res.append((char) c); c = next(); } while (!isSpaceChar(c)); return res.toString(); } public int nextInt() { int c = next(); while (isSpaceChar(c)) c = next(); int sgn = 1; if (c == '-') { sgn = -1; c = next(); } int res = 0; do { if (c < '0' || c > '9') throw new InputMismatchException(); res *= 10; res += c-'0'; c = next(); } while (!isSpaceChar(c)); return res * sgn; } public long nextLong() { int c = next(); while (isSpaceChar(c)) c = next(); long sgn = 1; if (c == '-') { sgn = -1; c = next(); } long res = 0; do { if (c < '0' || c > '9') throw new InputMismatchException(); res *= 10; res += c-'0'; c = next(); } while (!isSpaceChar(c)); return res * sgn; } public boolean isSpaceChar(int c) { return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1; } public interface SpaceCharFilter { public boolean isSpaceChar(int ch); } } static void debug(Object... o) { System.err.println(Arrays.deepToString(o)); } }
Submission Info
Submission Time | |
---|---|
Task | C - メンテナンス明け |
User | hamadu |
Language | Java (OpenJDK 1.7.0) |
Score | 100 |
Code Size | 7858 Byte |
Status | AC |
Exec Time | 1380 ms |
Memory | 44544 KB |
Compile Error
Note: ./Main.java uses unchecked or unsafe operations. Note: Recompile with -Xlint:unchecked for details.
Judge Result
Set Name | Subtask1 | Subtask2 | ||||
---|---|---|---|---|---|---|
Score / Max Score | 50 / 50 | 50 / 50 | ||||
Status |
|
|
Set Name | Test Cases |
---|---|
Subtask1 | small/00_sample00, small/00_sample01, small/00_sample02, small/10_small-0000, small/10_small-0001, small/10_small-0002, small/10_small-0003, small/10_small-0004, small/10_small-0005, small/10_small-0006, small/10_small-0007, small/10_small-0008, small/10_small-0009, small/10_small-0010, small/10_small-0011, small/10_small-0012, small/10_small-0013, small/10_small-0014, small/10_small-0015, small/10_small-0016, small/10_small-0017, small/10_small-0018, small/10_small-0019, small/30_max_small, small/40_simple_0000, small/40_simple_0001, small/40_simple_0002, small/40_simple_0003, small/40_simple_0004, small/40_simple_0005, small/40_simple_0006, small/40_simple_0007, small/40_simple_0008, small/40_simple_0009, small/40_simple_0010, small/40_simple_0011, small/40_simple_0012, small/40_simple_0013, small/40_simple_0014, small/40_simple_0015, small/40_simple_0016, small/40_simple_0017, small/40_simple_0018, small/40_simple_0019, small/90_dijkstra_killer_00, small/90_dijkstra_killer_01, small/91_tayama_killer_00, small/91_tayama_killer_01, small/91_tayama_killer_02, small/91_tayama_killer_03, small/91_tayama_killer_04, small/91_tayama_killer_05 |
Subtask2 | large/20_large-00, large/20_large-01, large/20_large-02, large/20_large-03, large/20_large-04, large/31_max_large |
Case Name | Status | Exec Time | Memory |
---|---|---|---|
large/20_large-00 | AC | 1308 ms | 41976 KB |
large/20_large-01 | AC | 1298 ms | 42360 KB |
large/20_large-02 | AC | 1380 ms | 41912 KB |
large/20_large-03 | AC | 1375 ms | 43392 KB |
large/20_large-04 | AC | 1379 ms | 44544 KB |
large/31_max_large | AC | 663 ms | 39632 KB |
small/00_sample00 | AC | 345 ms | 22512 KB |
small/00_sample01 | AC | 342 ms | 22544 KB |
small/00_sample02 | AC | 349 ms | 22536 KB |
small/10_small-0000 | AC | 426 ms | 26376 KB |
small/10_small-0001 | AC | 422 ms | 26544 KB |
small/10_small-0002 | AC | 413 ms | 26176 KB |
small/10_small-0003 | AC | 420 ms | 26288 KB |
small/10_small-0004 | AC | 417 ms | 26456 KB |
small/10_small-0005 | AC | 442 ms | 26268 KB |
small/10_small-0006 | AC | 424 ms | 26328 KB |
small/10_small-0007 | AC | 428 ms | 26532 KB |
small/10_small-0008 | AC | 419 ms | 26396 KB |
small/10_small-0009 | AC | 427 ms | 26400 KB |
small/10_small-0010 | AC | 419 ms | 26444 KB |
small/10_small-0011 | AC | 421 ms | 26296 KB |
small/10_small-0012 | AC | 439 ms | 26752 KB |
small/10_small-0013 | AC | 428 ms | 26512 KB |
small/10_small-0014 | AC | 420 ms | 26212 KB |
small/10_small-0015 | AC | 436 ms | 26400 KB |
small/10_small-0016 | AC | 422 ms | 26200 KB |
small/10_small-0017 | AC | 433 ms | 26468 KB |
small/10_small-0018 | AC | 436 ms | 26480 KB |
small/10_small-0019 | AC | 433 ms | 26456 KB |
small/30_max_small | AC | 394 ms | 25584 KB |
small/40_simple_0000 | AC | 321 ms | 22532 KB |
small/40_simple_0001 | AC | 326 ms | 22612 KB |
small/40_simple_0002 | AC | 325 ms | 22536 KB |
small/40_simple_0003 | AC | 322 ms | 22532 KB |
small/40_simple_0004 | AC | 321 ms | 22532 KB |
small/40_simple_0005 | AC | 374 ms | 22508 KB |
small/40_simple_0006 | AC | 333 ms | 22504 KB |
small/40_simple_0007 | AC | 339 ms | 22636 KB |
small/40_simple_0008 | AC | 329 ms | 22556 KB |
small/40_simple_0009 | AC | 335 ms | 22528 KB |
small/40_simple_0010 | AC | 339 ms | 22540 KB |
small/40_simple_0011 | AC | 343 ms | 22536 KB |
small/40_simple_0012 | AC | 332 ms | 22540 KB |
small/40_simple_0013 | AC | 337 ms | 22540 KB |
small/40_simple_0014 | AC | 338 ms | 22540 KB |
small/40_simple_0015 | AC | 334 ms | 22652 KB |
small/40_simple_0016 | AC | 339 ms | 22536 KB |
small/40_simple_0017 | AC | 336 ms | 22544 KB |
small/40_simple_0018 | AC | 350 ms | 22612 KB |
small/40_simple_0019 | AC | 333 ms | 22540 KB |
small/90_dijkstra_killer_00 | AC | 334 ms | 22540 KB |
small/90_dijkstra_killer_01 | AC | 336 ms | 22544 KB |
small/91_tayama_killer_00 | AC | 332 ms | 22524 KB |
small/91_tayama_killer_01 | AC | 338 ms | 22536 KB |
small/91_tayama_killer_02 | AC | 333 ms | 22608 KB |
small/91_tayama_killer_03 | AC | 392 ms | 22592 KB |
small/91_tayama_killer_04 | AC | 350 ms | 22520 KB |
small/91_tayama_killer_05 | AC | 381 ms | 22536 KB |