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
AC × 52
AC × 6
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