#1176432 (Java) No.654 Air E869120

• 問題: No.654 Air E869120
• ユーザー: 37zigen
• 提出日時: 2026-08-12 19:55:22
• 言語: Java (openjdk 25.0.2)
• 結果: AC
• 実行時間: 125 ms / 2,000 ms
• コード長: 19,376 bytes
• コンパイル時間: 2,052 ms
• コンパイル使用メモリ: 110,184 KB
• 実行使用メモリ: 48,172 KB
• 最終ジャッジ日時: 2026-08-12 19:55:29
• 合計ジャッジ時間: 7,152 ms
• ジャッジサーバーID （参考情報）: judge2_0 / judge3_0

ファイルパターン	結果
sample	AC * 5
other	AC * 35

ソースコード

import java.io.IOException;
import java.io.InputStream;
import java.io.OutputStream;
import java.io.PrintStream;
import java.io.PrintWriter;
import java.lang.reflect.Array;
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collection;
import java.util.Collections;
import java.util.Comparator;
import java.util.List;
import java.util.NoSuchElementException;
import java.util.Objects;
import java.util.PrimitiveIterator.OfInt;
import java.util.PrimitiveIterator.OfLong;
import java.util.PrimitiveIterator;
import java.util.Queue;
import java.util.Random;
import java.util.function.IntBinaryOperator;
import java.util.function.IntFunction;
import java.util.function.IntToDoubleFunction;
import java.util.function.IntToLongFunction;
import java.util.function.IntUnaryOperator;
import java.util.function.LongBinaryOperator;
import java.util.function.Predicate;
import java.util.function.ToIntFunction;
import java.util.random.RandomGenerator;
import java.util.stream.IntStream;
import java.util.stream.Stream;

public class Main {
    static MyPrintWriter pw = MyPrintWriter.getInstance();

    static FastScanner sc = FastScanner.getInstance();

    public static void main(String[] args) throws IOException {
        Thread.setDefaultUncaughtExceptionHandler((t, e) -> System.exit(1));
        new Main().run();
        pw.flush();
    }

    void run() {
        int N = sc.nextInt();
        int M = sc.nextInt();
        long d = sc.nextLong();
        int[] U = new int[M];
        int[] V = new int[M];
        long[] P = new long[M];
        long[] Q = new long[M];
        long[] W = new long[M];
        LongArrayList[] timesList = new LongArrayList[N];
        for (int i = 0; i < timesList.length; i++) {
            timesList[i] = new LongArrayList();
        }
        for (int i = 0; i < M; i++) {
            U[i] = sc.nextInt();
            V[i] = sc.nextInt();
            P[i] = sc.nextLong();
            Q[i] = sc.nextLong();
            W[i] = sc.nextLong();
            U[i]--;
            V[i]--;
            timesList[U[i]].add(P[i]);
            timesList[V[i]].add(Q[i]);
        }
        int destination = Integer.MAX_VALUE;
        timesList[N - 1].add(destination);
        long[][] times = new long[N][];
        long[] cnt = new long[N];
        for (int i = 0; i < N; i++) {
            times[i] = timesList[i].toArray();
            times[i] = ArrayUtils.sortq(times[i]);
            cnt[i] = times[i].length;
        }
        var cntSum = ArrayUtils.prefixSumFromZERO(cnt);
        MaxFlow mf = new MaxFlow(((int) (cntSum[cntSum.length - 1])) + 1);
        for (int i = 0; i < M; i++) {
            int src = U[i];
            int dst = V[i];
            int from = ((int) (cntSum[src] + SortedArrays.indexOf(times[src], P[i])));
            int to = ((int) (cntSum[dst] + SortedArrays.ceil(times[dst], Q[i] + d)));
            if (to == cntSum[dst + 1]) {
                continue;
            }
            mf.addEdge(from, to, W[i]);
        }
        long infCap = Long.MAX_VALUE / 3;
        for (int i = 0; i < N; i++) {
            for (int j = 0; (j + 1) < cnt[i]; j++) {
                mf.addEdge(((int) (cntSum[i] + j)), ((int) ((cntSum[i] + j) + 1)), infCap);
            }
        }
        int sink = ((int) (cntSum[N - 1] + SortedArrays.indexOf(times[N - 1], destination)));
        long ans = mf.maxFlowValue(0, sink);
        pw.println(ans);
        // mf.draw();
    }
}

class ArrayUtils {
    /**
     * b[i] = a[1] + a[2] + .. + a[i - 1]
     *
     * @param a
     * @return  */
    public static long[] prefixSumFromZERO(long[] a) {
        long[] b = new long[a.length + 1];
        for (int i = 1; i < b.length; ++i) {
            b[i] = b[i - 1] + a[i - 1];
        }
        return b;
    }

    public static long[] sortq(long[] a) {
        if (a.length == 0) {
            return new long[0];
        }
        long[] b = a.clone();
        Arrays.sort(b);
        int pointer = 1;
        for (int i = 1; i < b.length; i++) {
            if (b[pointer - 1] != b[i]) {
                b[pointer++] = b[i];
            }
        }
        return Arrays.copyOf(b, pointer);
    }
}

class FastScanner {
    private static FastScanner instance = null;

    private final InputStream in = System.in;

    private final byte[] buffer = new byte[1 << 16];

    private int ptr = 0;

    private int buflen = 0;

    private FastScanner() {
    }

    public static FastScanner getInstance() {
        if (instance == null) {
            instance = new FastScanner();
        }
        return instance;
    }

    private boolean hasNextByte() {
        if (ptr < buflen) {
            return true;
        }
        ptr = 0;
        try {
            buflen = in.read(buffer);
        } catch (IOException e) {
            e.printStackTrace();
        }
        return buflen > 0;
    }

    private int readByte() {
        if (hasNextByte()) {
            return buffer[ptr++];
        } else {
            return -1;
        }
    }

    private boolean isPrintableChar(int c) {
        return (33 <= c) && (c <= 126);
    }

    public boolean hasNext() {
        while (hasNextByte() && (!isPrintableChar(buffer[ptr]))) {
            ptr++;
        } 
        return hasNextByte();
    }

    public long nextLong() {
        if (!hasNext()) {
            throw new NoSuchElementException();
        }
        long n = 0;
        boolean minus = false;
        int b = readByte();
        if (b == '-') {
            minus = true;
            b = readByte();
        }
        while ((b >= '0') && (b <= '9')) {
            // n = n * 10 + (b - '0');
            n = ((n << 1) + (n << 3)) + (b - '0');
            b = readByte();
        } 
        return minus ? -n : n;
    }

    public int nextInt() {
        return ((int) (nextLong()));
    }
}

/**
 * *
 * lenがa.lengthに比べて小さくなっても配列を取り直さない。
 *
 * @param <T>
 */
class IntDeque implements Iterable<Integer> {
    @SuppressWarnings("unchecked")
    int[] a = new int[16];

    int head = 0;

    int tail = 0;

    int len = 0;

    // [head, tail)に値を持つ。
    public IntDeque() {
    }

    public void addLast(int v) {
        if (len == a.length) {
            resize(2 * len);
        }
        a[tail] = v;
        tail = (tail + 1) & (a.length - 1);
        ++len;
    }

    public int pollFirst() {
        if (len == 0) {
            throw new NoSuchElementException();
        }
        int ret = a[head];
        head = (head + 1) & (a.length - 1);
        len--;
        return ret;
    }

    public boolean isEmpty() {
        return len == 0;
    }

    public int get(int id) {
        if ((id < 0) || (id >= len)) {
            throw new IndexOutOfBoundsException(((((("get(" + id) + ")は添え字") + 0) + "以上") + (len - 1)) + "以下に違反");
        }
        return a[(head + id) & (a.length - 1)];
    }

    void resize(int size) {
        @SuppressWarnings("unchecked")
        int[] na = new int[size];
        for (int i = 0; i < len; i++) {
            na[i] = a[(head + i) & (a.length - 1)];
        }
        head = 0;
        tail = len;
        a = na;
    }

    @Override
    public PrimitiveIterator.OfInt iterator() {
        return new PrimitiveIterator.OfInt() {
            int idx = 0;

            @Override
            public boolean hasNext() {
                return idx < len;
            }

            @Override
            public int nextInt() {
                if (!hasNext()) {
                    throw new NoSuchElementException();
                }
                return get(idx++);
            }
        };
    }

    /**
     * デックの内容を表す文字列を返す。
     *
     * @return デック内容の文字列
    $O(N)$
    // 未テスト
     */
    @Override
    public String toString() {
        StringBuilder sb = new StringBuilder();
        sb.append("[");
        for (int i = 0; i < len; i++) {
            sb.append(get(i));
            if (i < (len - 1)) {
                sb.append(", ");
            }
        }
        sb.append("]");
        return sb.toString();
    }

    /**
     * このデックと別のオブジェクトの同値性を判定します。
     * 全ての要素が順序を含めて一致する場合に同値とみなします。
     *
     * <p>計算量: $O(N)$（$N$ はデックの要素数）</p>
     *
     * @param obj
     * 		比較対象のオブジェクト
     * @return 同値であれば true, そうでなければ false
     */
    // 未テスト
    @Override
    public boolean equals(Object obj) {
        if (this == obj) {
            return true;
        }
        if (!(obj instanceof IntDeque)) {
            return false;
        }
        IntDeque other = ((IntDeque) (obj));
        if (this.len != other.len) {
            return false;
        }
        for (int i = 0; i < len; i++) {
            if (this.get(i) != other.get(i)) {
                return false;
            }
        }
        return true;
    }

    /**
     * このデックのハッシュコードを計算します。
     *
     * <p>計算量: $O(N)$（$N$ はデックの要素数）</p>
     *
     * @return ハッシュコード
     */
    // 未テスト
    @Override
    public int hashCode() {
        int result = 1;
        for (int i = 0; i < len; i++) {
            result = (31 * result) + Integer.hashCode(get(i));
        }
        return result;
    }
}

/**
 * *
 * lenがa.lengthに比べて小さくなっても配列を取り直さない。
 */
class LongArrayList implements Iterable<Long> {
    @SuppressWarnings("unchecked")
    long[] a;

    int tail = 0;

    int len = 0;

    int capacity = 16;

    public LongArrayList() {
        a = new long[capacity];
    }

    public void add(long v) {
        if (len == a.length) {
            resize(2 * len);
        }
        a[tail] = v;
        tail++;
        ++len;
    }

    public long get(int id) {
        if ((id < 0) || (id >= len)) {
            throw new IndexOutOfBoundsException(((((("get(" + id) + ")は添え字") + 0) + "以上") + (len - 1)) + "以下に違反");
        }
        return a[id];
    }

    void resize(int size) {
        a = Arrays.copyOf(a, size);
        tail = len;
    }

    public long[] toArray() {
        return Arrays.copyOf(a, len);
    }

    @Override
    public PrimitiveIterator.OfLong iterator() {
        return new PrimitiveIterator.OfLong() {
            int idx = 0;

            @Override
            public boolean hasNext() {
                return idx < len;
            }

            @Override
            public long nextLong() {
                if (!hasNext()) {
                    throw new NoSuchElementException();
                }
                return get(idx++);
            }
        };
    }

    /**
     * 内部状態を文字列として表す。
     * <ul>
     * <li>事前条件: 特になし。</li>
     * <li>事後条件: 特になし。</li>
     * <li>計算量: $O(N)$</li>
     * <li>破壊的変更: なし。</li>
     * </ul>
     *
     * @return 内部状態の文字列表現
     */
    // 未テスト
    @Override
    public String toString() {
        return ("LongArrayList { elements: " + Arrays.toString(toArray())) + " }";
    }
}

class MaxFlow {
    public class Edge {
        public final int v;

        public final long cap;

        public long flow;// flowは非負。 flowとie.flowの高々一方のみが正。


        final int invEdgeId;

        public Edge(int v, long cap, int invEdgeId) {
            this.v = v;
            this.cap = cap;
            this.invEdgeId = invEdgeId;
        }

        long res() {
            return (cap - flow) + g[v].get(invEdgeId).flow;
        }
    }

    int n;

    public ArrayList<Edge>[] g;

    @SuppressWarnings("unchecked")
    public MaxFlow(int n) {
        this.n = n;
        g = new ArrayList[n];
        Arrays.setAll(g, i -> new ArrayList<>());
    }

    public void addEdge(int u, int v, long cap) {
        if (cap < 0) {
            throw new AssertionError();
        }
        Edge e = new Edge(v, cap, g[v].size());
        Edge ie = new Edge(u, 0, g[u].size());
        g[u].add(e);
        g[v].add(ie);
    }

    int[] d;

    int[] itr;

    int s;

    int t;

    /**
     * 一度最大流を求めた後に、辺を追加して再度呼び出すと、追加でいくつ流せるかが返される。
     * O(N^2 M)
     *
     * @param s
     * @param t
     * @return verified:https://atcoder.jp/contests/abc263/submissions/71027612
     */
    public long maxFlowValue(int s, int t) {
        return maxFlowValue(s, t, Long.MAX_VALUE / 3);
    }

    /**
     * 最大流量がcutoff以上になったら打ち切る。
     *
     * @param s
     * @param t
     * @param cutoff
     * @return verified:https://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=11030642#1
     */
    public long maxFlowValue(int s, int t, long cutoff) {
        if (s == t) {
            return 0;
        }
        this.s = s;
        this.t = t;
        long ans = 0;
        d = new int[n];
        itr = new int[n];
        while (ans < cutoff) {
            IntDeque que = new IntDeque();
            que.addLast(s);
            Arrays.fill(itr, 0);
            Arrays.fill(d, n + 1);
            d[s] = 0;
            // 残余ネットワークで最短路を求める
            while (!que.isEmpty()) {
                int v = que.pollFirst();
                if (v == t) {
                    break;
                }
                for (Edge e : g[v]) {
                    if ((d[e.v] == (n + 1)) && (e.res() > 0)) {
                        d[e.v] = d[v] + 1;
                        que.addLast(e.v);
                    }
                }
            } 
            if (d[t] == (n + 1)) {
                break;
            }
            // 最短路上でフローを流す
            while (ans < cutoff) {
                // 一回につき飽和辺が一つ以上増えるので、高々O(E)回周る。
                long add = dfs(s, cutoff - ans);
                ans += add;
                if (add == 0) {
                    break;
                }
            } 
        } 
        return Math.min(ans, cutoff);
    }

    private long dfs(int v, long upper) {
        if (v == t) {
            return upper;
        }
        while (itr[v] < g[v].size()) {
            Edge e = g[v].get(itr[v]);
            if ((e.res() > 0) && (d[e.v] == (d[v] + 1))) {
                long add = dfs(e.v, Math.min(upper, e.res()));
                if (add != 0) {
                    var ie = g[e.v].get(e.invEdgeId);
                    long add0 = Math.min(ie.flow, add);
                    ie.flow -= add0;
                    e.flow += add - add0;
                    return add;
                }
            }
            itr[v]++;// e.res()>0&&d[e.v]==d[v]+1はdfsでflowを一回流しただけで満たされなくなるとは限らないなので、ifの前ではなくifの後に呼ぶ。ifの前に置くと遅い。

        } 
        return 0;
    }
}

class MyPrintWriter extends PrintWriter {
    private static MyPrintWriter instance = null;

    private MyPrintWriter() {
        super(System.out);
    }

    public static MyPrintWriter getInstance() {
        if (instance == null) {
            instance = new MyPrintWriter();
        }
        return instance;
    }
}

class SortedArrays {
    /**
     * key > a[i] となる最大の i を返す。aはソートされているとする。
     *
     * @param a
     * @param key
     * @return  */
    public static int lower(long[] a, long key) {
        int ok = -1;
        int ng = a.length;
        while ((ng - ok) > 1) {
            int m = (ok + ng) / 2;
            if (key > a[m]) {
                ok = m;
            } else {
                ng = m;
            }
        } 
        return ok;
    }

    /**
     * key <= a[i] となる最小の i を返す。
     *
     * @param a
     * @param key
     * @return  */
    public static int ceil(long[] a, long key) {
        int ok = a.length;
        int ng = -1;
        while ((ok - ng) > 1) {
            int m = (ok + ng) / 2;
            if (a[m] >= key) {
                ok = m;
            } else {
                ng = m;
            }
        } 
        return ok;
    }

    /**
     * key = a[i] となる最小の i を返す。存在しなければ-1
     * 未テスト
     *
     * @param a
     * @param key
     * @return  */
    public static int indexOf(long[] a, long key) {
        int ret = lower(a, key) + 1;
        if (((0 <= ret) && (ret < a.length)) && (a[ret] == key)) {
            return ret;
        } else {
            return -1;
        }
    }
}


// --- Original Code ---
// 
// 
// import java.io.IOException;
// import java.util.Arrays;
// 
// import library.tools.FastScanner;
// import library.tools.MergeFiles;
// import library.tools.MyPrintWriter;
// import library.util.ArrayUtils;
// import library.util.collections.LongArrayList;
// import library.util.graph.MaxFlow;
// import library.util.seq.SortedArrays;
// 
// public class Main {
// 	static MyPrintWriter pw = MyPrintWriter.getInstance();
// 	static FastScanner sc = FastScanner.getInstance();
// 
// 	public static void main(String[] args) throws IOException {
// 		new Main().run();
// 		pw.flush();
// 		MergeFiles.export();
// 	}
// 	
// 
// 	void run() {
// 		int N=sc.nextInt();
// 		int M=sc.nextInt();
// 		long d=sc.nextLong();
// 		int[]U=new int[M];
// 		int[]V=new int[M];
// 		long[]P=new long[M];
// 		long[]Q=new long[M];
// 		long[]W=new long[M];
// 		LongArrayList[] timesList=new LongArrayList[N];
// 		for (int i = 0; i < timesList.length; i++) {
// 			timesList[i]=new LongArrayList();
// 		}
// 		for (int i = 0; i < M; i++) {
// 			U[i]=sc.nextInt();
// 			V[i]=sc.nextInt();
// 			P[i]=sc.nextLong();
// 			Q[i]=sc.nextLong();
// 			W[i]=sc.nextLong();
// 			U[i]--;
// 			V[i]--;
// 			timesList[U[i]].add(P[i]);
// 			timesList[V[i]].add(Q[i]);
// 		}
// 		int destination = Integer.MAX_VALUE;
// 		timesList[N - 1].add(destination);
// 		
// 		long[][] times=new long[N][];
// 		long[]cnt=new long[N];
// 		for (int i = 0; i < N; i++) {
// 			times[i]=timesList[i].toArray();
// 			times[i]=ArrayUtils.sortq(times[i]);
// 			cnt[i]=times[i].length;
// 		}
// 		var cntSum=ArrayUtils.prefixSumFromZERO(cnt);
// 		MaxFlow mf=new MaxFlow((int)cntSum[cntSum.length-1] + 1);
// 		for (int i = 0; i < M; i++) {
// 			int src=U[i];
// 			int dst=V[i];
// 			int from = (int) (cntSum[src] + SortedArrays.indexOf(times[src], P[i]));
// 			int to = (int) (cntSum[dst] + SortedArrays.ceil(times[dst], Q[i] + d));
// 			if (to == cntSum[dst + 1]) continue;
// 			mf.addEdge(from, to, W[i]);
// 		}
// 		long infCap = Long.MAX_VALUE/3;
// 		for (int i = 0; i < N; i++) {
// 			for (int j = 0; j + 1 < cnt[i]; j++) {
// 				mf.addEdge((int)(cntSum[i] + j), (int)(cntSum[i] + j + 1), infCap);
// 			}
// 		}
// 		int sink = (int)(cntSum[N - 1] + SortedArrays.indexOf(times[N - 1], destination));
// 		long ans=mf.maxFlowValue(0, sink);
// 		pw.println(ans);
// //		mf.draw();
// 	}
//     
// 	void tr(Object... objects) {
// 		System.out.println(Arrays.deepToString(objects));
// 	}
// }
//