結果

問題 No.654 Air E869120
ユーザー denderaKawazudenderaKawazu
提出日時 2019-01-24 18:00:07
言語 Java21
(openjdk 21)
結果
WA  
実行時間 -
コード長 7,116 bytes
コンパイル時間 3,465 ms
コンパイル使用メモリ 85,320 KB
実行使用メモリ 56,220 KB
最終ジャッジ日時 2024-09-16 04:39:46
合計ジャッジ時間 8,577 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge6
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 70 ms
51,108 KB
testcase_01 AC 68 ms
50,924 KB
testcase_02 AC 68 ms
51,100 KB
testcase_03 AC 71 ms
50,904 KB
testcase_04 AC 70 ms
50,860 KB
testcase_05 AC 69 ms
51,032 KB
testcase_06 AC 68 ms
51,060 KB
testcase_07 AC 70 ms
51,112 KB
testcase_08 AC 72 ms
51,060 KB
testcase_09 AC 69 ms
51,168 KB
testcase_10 AC 172 ms
55,604 KB
testcase_11 AC 158 ms
55,784 KB
testcase_12 AC 158 ms
55,808 KB
testcase_13 AC 167 ms
56,060 KB
testcase_14 AC 157 ms
55,512 KB
testcase_15 AC 159 ms
55,920 KB
testcase_16 AC 154 ms
55,360 KB
testcase_17 AC 148 ms
55,364 KB
testcase_18 AC 148 ms
53,316 KB
testcase_19 WA -
testcase_20 WA -
testcase_21 WA -
testcase_22 AC 125 ms
53,944 KB
testcase_23 AC 130 ms
53,704 KB
testcase_24 WA -
testcase_25 AC 122 ms
53,680 KB
testcase_26 AC 123 ms
53,632 KB
testcase_27 AC 120 ms
53,000 KB
testcase_28 AC 122 ms
53,420 KB
testcase_29 AC 120 ms
53,076 KB
testcase_30 AC 104 ms
52,696 KB
testcase_31 AC 113 ms
52,560 KB
testcase_32 AC 114 ms
52,608 KB
testcase_33 AC 104 ms
52,640 KB
testcase_34 AC 104 ms
53,032 KB
testcase_35 AC 68 ms
51,088 KB
testcase_36 AC 67 ms
51,068 KB
testcase_37 AC 69 ms
51,028 KB
testcase_38 AC 67 ms
50,756 KB
testcase_39 AC 68 ms
50,984 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

import java.io.OutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.Arrays;
import java.util.Collection;
import java.util.InputMismatchException;
import java.io.IOException;
import java.util.ArrayList;
import java.util.Queue;
import java.util.Comparator;
import java.util.ArrayDeque;
import java.io.InputStream;

/**
 * Built using CHelper plug-in
 * Actual solution is at the top
 */
public class Main {
    public static void main(String[] args) {
        InputStream inputStream = System.in;
        OutputStream outputStream = System.out;
        FastScanner in = new FastScanner(inputStream);
        PrintWriter out = new PrintWriter(outputStream);
        Task solver = new Task();
        solver.solve(1, in, out);
        out.close();
    }

    static class Task {
        public void solve(int testNumber, FastScanner in, PrintWriter out) {
            int n = in.nextInt();
            int m = in.nextInt();
            int d = in.nextInt();

            Task.Schedule[] schedules = new Task.Schedule[m];
            for (int i = 0; i < m; i++)
                schedules[i] = new Task.Schedule(in.nextInt(), in.nextInt(), in.nextInt(), in.nextInt(), in.nextLong());
            Arrays.sort(schedules, Comparator.comparing(Task.Schedule::getP));

            Dinic dinic = new Dinic(m + 2);
            for (int i = 0; i < m; i++) {
                Task.Schedule cs = schedules[i];
                int t = cs.getQ() + d;
                if (cs.getU() == 1)
                    dinic.setEdge(m, i, cs.getW());
                if (cs.getV() == n) {
                    dinic.setEdge(i, m + 1, cs.getW());
                    continue;
                }
                for (int j = m - 1; schedules[j].getP() >= t; j--) {
                    if (schedules[j].getU() == cs.getV()) {
                        dinic.setEdge(i, j, cs.getW());
                    }
                }
            }

            out.println(dinic.getMaxFlow(m, m + 1));
        }

        static class Schedule {
            int u;
            int v;
            int p;
            int q;
            long w;

            Schedule(int u, int v, int p, int q, long w) {
                this.u = u;
                this.v = v;
                this.p = p;
                this.q = q;
                this.w = w;
            }

            public int getU() {
                return u;
            }

            public int getV() {
                return v;
            }

            public int getP() {
                return p;
            }

            public int getQ() {
                return q;
            }

            public long getW() {
                return w;
            }

        }

    }

    static class FastScanner {
        private InputStream in;
        private byte[] buffer = new byte[1024];
        private int bufPointer;
        private int bufLength;

        public FastScanner(InputStream in) {
            this.in = in;
        }

        private int readByte() {
            if (bufPointer >= bufLength) {
                if (bufLength == -1)
                    throw new InputMismatchException();

                bufPointer = 0;
                try {
                    bufLength = in.read(buffer);
                } catch (IOException e) {
                    throw new InputMismatchException();
                }

                if (bufLength <= 0)
                    return -1;
            }
            return buffer[bufPointer++];
        }

        private static boolean isSpaceChar(int c) {
            return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
        }

        public long nextLong() {
            long n = 0;

            int b = readByte();
            while (isSpaceChar(b))
                b = readByte();

            boolean minus = (b == '-');
            if (minus)
                b = readByte();

            while (b >= '0' && b <= '9') {
                n *= 10;
                n += b - '0';
                b = readByte();
            }

            if (!isSpaceChar(b))
                throw new NumberFormatException();

            return minus ? -n : n;
        }

        public int nextInt() {
            long n = nextLong();

            if (n < Integer.MIN_VALUE || n > Integer.MAX_VALUE)
                throw new NumberFormatException();

            return (int) n;
        }

    }

    static class Dinic {
        private ArrayList<Dinic.Edge>[] graph;
        private int[] dist;
        private int[] start;

        public Dinic(int vertexNum) {
            dist = new int[vertexNum];
            start = new int[vertexNum];
            graph = new ArrayList[vertexNum];
            for (int i = 0; i < vertexNum; i++)
                graph[i] = new ArrayList<>();
        }

        public void setEdge(int from, int to, long cap) {
            Dinic.Edge e = new Dinic.Edge(to, cap);
            e.rev = new Dinic.Edge(from, 0, e);
            graph[from].add(e);
            graph[to].add(e.rev);
        }

        public long getMaxFlow(int source, int sink) {
            long flow = 0;
            while (true) {
                setDistBFS(source);
                if (dist[sink] == -1)
                    return flow;
                Arrays.fill(start, 0);
                long df = sendFlowDFS(source, sink, Long.MAX_VALUE);
                while (df > 0) {
                    flow += df;
                    df = sendFlowDFS(source, sink, Long.MAX_VALUE);
                }
            }
        }

        private void setDistBFS(int zero) {
            Arrays.fill(dist, -1);
            dist[zero] = 0;
            Queue<Integer> vq = new ArrayDeque<>();
            vq.add(zero);
            while (!vq.isEmpty()) {
                int cv = vq.poll();
                for (Dinic.Edge e : graph[cv]) {
                    if (e.cap > 0 && dist[e.to] == -1) {
                        dist[e.to] = dist[cv] + 1;
                        vq.add(e.to);
                    }
                }
            }
        }

        private long sendFlowDFS(int cv, int source, long flow) {
            if (cv == source)
                return flow;
            while (start[cv] < graph[cv].size()) {
                Dinic.Edge e = graph[cv].get(start[cv]);
                if (e.cap > 0 && dist[cv] < dist[e.to]) {
                    long d = sendFlowDFS(e.to, source, Math.min(e.cap, flow));
                    if (d > 0) {
                        e.cap -= d;
                        e.rev.cap += d;
                        return d;
                    }
                }
                start[cv]++;
            }
            return 0;
        }

        private static class Edge {
            int to;
            Dinic.Edge rev;
            long cap;

            Edge(int to, long cap) {
                this.to = to;
                this.cap = cap;
            }

            Edge(int to, long cap, Dinic.Edge rev) {
                this.to = to;
                this.cap = cap;
                this.rev = rev;
            }

        }

    }
}
0