結果
問題 | No.5015 Escape from Labyrinth |
ユーザー | Yu_212 |
提出日時 | 2023-04-16 17:07:25 |
言語 | Java21 (openjdk 21) |
結果 |
WA
|
実行時間 | - |
コード長 | 24,929 bytes |
コンパイル時間 | 3,533 ms |
コンパイル使用メモリ | 94,604 KB |
実行使用メモリ | 70,760 KB |
スコア | 167,450 |
最終ジャッジ日時 | 2023-04-16 17:12:22 |
合計ジャッジ時間 | 293,140 ms |
ジャッジサーバーID (参考情報) |
judge12 / judge13 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2,846 ms
70,328 KB |
testcase_01 | AC | 2,813 ms
70,228 KB |
testcase_02 | AC | 2,819 ms
70,060 KB |
testcase_03 | AC | 2,805 ms
70,216 KB |
testcase_04 | AC | 2,820 ms
70,656 KB |
testcase_05 | AC | 2,848 ms
70,576 KB |
testcase_06 | AC | 2,818 ms
69,764 KB |
testcase_07 | WA | - |
testcase_08 | AC | 2,789 ms
70,076 KB |
testcase_09 | AC | 2,789 ms
70,316 KB |
testcase_10 | AC | 2,824 ms
70,020 KB |
testcase_11 | AC | 2,836 ms
69,920 KB |
testcase_12 | AC | 2,792 ms
69,876 KB |
testcase_13 | AC | 2,807 ms
70,516 KB |
testcase_14 | AC | 2,780 ms
69,952 KB |
testcase_15 | AC | 2,857 ms
70,576 KB |
testcase_16 | AC | 2,794 ms
69,668 KB |
testcase_17 | AC | 2,812 ms
70,168 KB |
testcase_18 | AC | 2,838 ms
70,196 KB |
testcase_19 | AC | 2,791 ms
69,808 KB |
testcase_20 | AC | 2,815 ms
69,980 KB |
testcase_21 | WA | - |
testcase_22 | AC | 2,829 ms
70,416 KB |
testcase_23 | AC | 2,797 ms
69,924 KB |
testcase_24 | AC | 2,796 ms
69,700 KB |
testcase_25 | AC | 2,816 ms
69,732 KB |
testcase_26 | AC | 2,796 ms
69,904 KB |
testcase_27 | AC | 2,809 ms
70,092 KB |
testcase_28 | AC | 2,825 ms
70,292 KB |
testcase_29 | AC | 2,807 ms
69,844 KB |
testcase_30 | AC | 2,941 ms
69,704 KB |
testcase_31 | AC | 2,785 ms
70,464 KB |
testcase_32 | AC | 2,818 ms
70,500 KB |
testcase_33 | AC | 2,792 ms
70,092 KB |
testcase_34 | AC | 2,800 ms
69,784 KB |
testcase_35 | AC | 2,813 ms
70,028 KB |
testcase_36 | AC | 2,834 ms
69,984 KB |
testcase_37 | AC | 2,851 ms
69,688 KB |
testcase_38 | AC | 2,855 ms
70,152 KB |
testcase_39 | AC | 2,801 ms
70,024 KB |
testcase_40 | AC | 2,808 ms
70,228 KB |
testcase_41 | AC | 2,840 ms
69,924 KB |
testcase_42 | AC | 2,811 ms
69,888 KB |
testcase_43 | AC | 2,783 ms
69,856 KB |
testcase_44 | AC | 2,774 ms
69,344 KB |
testcase_45 | AC | 2,845 ms
70,384 KB |
testcase_46 | AC | 2,781 ms
69,780 KB |
testcase_47 | AC | 2,834 ms
69,796 KB |
testcase_48 | AC | 2,830 ms
69,816 KB |
testcase_49 | AC | 2,807 ms
70,332 KB |
testcase_50 | AC | 2,858 ms
70,140 KB |
testcase_51 | AC | 2,818 ms
70,100 KB |
testcase_52 | AC | 2,809 ms
70,268 KB |
testcase_53 | AC | 2,799 ms
70,076 KB |
testcase_54 | AC | 2,858 ms
70,036 KB |
testcase_55 | AC | 2,852 ms
70,380 KB |
testcase_56 | AC | 2,855 ms
69,996 KB |
testcase_57 | AC | 2,821 ms
69,992 KB |
testcase_58 | WA | - |
testcase_59 | AC | 2,772 ms
69,356 KB |
testcase_60 | AC | 2,808 ms
70,188 KB |
testcase_61 | AC | 2,828 ms
69,908 KB |
testcase_62 | AC | 2,833 ms
70,068 KB |
testcase_63 | AC | 2,840 ms
68,484 KB |
testcase_64 | WA | - |
testcase_65 | AC | 2,848 ms
70,184 KB |
testcase_66 | AC | 2,818 ms
70,324 KB |
testcase_67 | AC | 2,843 ms
70,236 KB |
testcase_68 | AC | 2,811 ms
69,668 KB |
testcase_69 | AC | 2,818 ms
70,392 KB |
testcase_70 | AC | 2,813 ms
70,760 KB |
testcase_71 | AC | 2,810 ms
69,812 KB |
testcase_72 | AC | 2,801 ms
69,924 KB |
testcase_73 | AC | 2,805 ms
70,172 KB |
testcase_74 | AC | 2,782 ms
70,084 KB |
testcase_75 | AC | 2,830 ms
70,612 KB |
testcase_76 | AC | 2,836 ms
69,900 KB |
testcase_77 | AC | 2,819 ms
70,260 KB |
testcase_78 | AC | 2,789 ms
70,536 KB |
testcase_79 | AC | 2,795 ms
69,960 KB |
testcase_80 | AC | 2,809 ms
70,572 KB |
testcase_81 | AC | 2,792 ms
70,224 KB |
testcase_82 | AC | 2,791 ms
70,568 KB |
testcase_83 | AC | 2,815 ms
69,856 KB |
testcase_84 | AC | 2,792 ms
69,784 KB |
testcase_85 | AC | 2,826 ms
70,324 KB |
testcase_86 | AC | 2,842 ms
69,860 KB |
testcase_87 | AC | 2,880 ms
70,380 KB |
testcase_88 | AC | 2,798 ms
70,296 KB |
testcase_89 | AC | 2,782 ms
70,436 KB |
testcase_90 | AC | 2,797 ms
69,776 KB |
testcase_91 | AC | 2,811 ms
69,440 KB |
testcase_92 | WA | - |
testcase_93 | AC | 2,791 ms
67,652 KB |
testcase_94 | AC | 2,783 ms
70,512 KB |
testcase_95 | AC | 2,800 ms
70,384 KB |
testcase_96 | AC | 2,841 ms
69,688 KB |
testcase_97 | AC | 2,834 ms
70,068 KB |
testcase_98 | AC | 2,786 ms
70,192 KB |
testcase_99 | AC | 2,793 ms
70,088 KB |
ソースコード
import java.io.*; import java.util.*; import java.util.concurrent.ThreadLocalRandom; import java.util.function.IntUnaryOperator; import java.util.function.LongUnaryOperator; import java.util.stream.Collectors; public class Main { static boolean isLocal; Random rand = new Random(); In in = new In(System.in); PrintStream out = System.out; long inf = 0x1fffffffffffffffL; int iinf = 0x3fffffff; long startTime; public static final int N = 60; public int D; public static final int H = 1500; public int M; public int J; public char[] grid; public Pos[] ps; public int[] ds; public Pos[] jps; int[][] distances; boolean[][] beam = new boolean[60][N * N]; int[] avgWait = new int[N * N]; int[] jid = new int[N * N]; public static final String[] ss = {"M L", "M U", "M R", "M D", "S"}; long solve(int seed) { startTime = System.currentTimeMillis(); in(); distances = new int[J+3][J+3]; for (int i = 0; i < J + 3; i++) { Arrays.fill(distances[i], iinf); } for (int i = 0; i < M; i++) { for (int d = 0; d < 4; d++) { Pos cur = ps[i]; while (true) { cur = cur.moved((d+2)%4); if (cur == null || grid[cur.z] == '#') { break; } for (int j = 0; j < 60; j += ds[i]) { beam[j][cur.z] = true; } } } } for (int i = 0; i < N * N; i++) { int c = 1; for (int j = 0; j < 60; j++) { if (beam[j][i]) { c++; } else { c = 1; } avgWait[i] += c; } } for (int i = 0; i < J + 3; i++) { calcDist(i); } // BitSet visited = new BitSet(J + 3); // visited.set(J); // visited.set(J + 1); // visited.set(J + 2); // List<Integer> routes = new ArrayList<>(); // routes.add(J); // routes.add(J + 1); // routes.add(J + 2); // int dsum = distances[J][J+1] + distances[J+1][J+2]; // int c = 0; // while (elapsed() < 2000) { // int p; // do { // p = rand.next(0, J); // } while (visited.get(p)); // int bi = -1; // int bd = iinf; // for (int i = 1; i < routes.size(); i++) { // int f = routes.get(i - 1); // int t = routes.get(i); // int diff = distances[f][p] + distances[p][t] - distances[f][t]; // if (bd > diff) { // bd = diff; // bi = i; // } // } // if (bi == -1) { // continue; // } //// debug(p, bi, bd, dsum); // if (routes.size() >= 200) { // break; // } //// if (dsum + bd * MUL[D] >= 60 * 500) { ////// c++; ////// if (c >= 100) { ////// break; ////// } else { ////// continue; ////// } //// continue; //// } // visited.set(p); // dsum += bd; // routes.add(bi, p); // } debug("?", elapsed()); State result = annealing(new State(), 180*10, 180, 2500); List<Integer> routes = result.routes; debug("?", elapsed()); Pos p = jps[J]; int tt = 0; int ds1 = 0; int ds2 = 0; for (int i = 1; i < routes.size(); i++) { Result res = route(jps[routes.get(i - 1)], jps[routes.get(i)], tt); // debug(distances[routes.get(i - 1)][routes.get(i)], res.damage * 60); ds1 += distances[routes.get(i - 1)][routes.get(i)]; ds2 += res.damage; // debug(p, res.from, res.to, res.damage); res.out(p, tt); tt = (tt + res.time) % 60; p = res.to; } debug(D, result.dsum, ds1, result.dsum/60, ds1/60, ds2, ds2*60./result.dsum); // if (ds2 > 1450) { // debug("!"); // throw new RuntimeException(); // } debug(ds2, totalCost, routes.size() * 10); return routes.size() * 10L; // List<Result> routes = new ArrayList<>(); // routes.add(route(jps[J], jps[J + 1], 0)); // routes.add(route(jps[J + 1], jps[J + 2], routes.get(0).time)); // int dsum = routes.get(0).damage + routes.get(1).damage; // while (true) { // int p; // do { // p = rand.next(0, J); // } while (visited.get(p)); // int tt = 0; // int bi = 0; // int bd = iinf; // Result br1 = null, br2 = null; // for (int i = 0; i < routes.size(); i++) { // Result r = routes.get(i); // Result r1 = route(r.from, jps[p], tt); // Result r2 = route(jps[p], r.to, (tt + r.time) % 60); // int diff = r1.damage + r2.damage - r.damage; // if (bd > diff) { // bd = diff; // bi = i; // br1 = r1; // br2 = r2; // } // tt = (tt + r.time) % 60; // } // debug(p, bi, bd, dsum); // if (dsum + bd >= 700) { // break; // } // visited.set(p); // dsum += bd; // routes.set(bi, br1); // routes.add(bi + 1, br2); // } // Pos p = jps[J]; // int tt = 0; // for (Result res : routes) { // debug(p, res.from, res.to); // res.out(p, tt); // tt = (tt + res.time) % 60; // p = res.to; // } // visited.set(J + 2); // visited.set(J); // tt = moveTo(J, J+1, tt, visited); // visited.clear(J + 2); // tt = moveTo(J+1, J+2, tt, visited); } //1678 int totalCost = 0; // int moveTo(int s, int g, int tt, BitSet visited) { // int cur = s; // int ds = 0; // while (cur != g) { // int md = iinf; // int mi = -1; // for (int i = 0; i < J + 3; i++) { // if (visited.get(i)) { // continue; // } //// debug(i, cur, jps[i].dist(jps[g]), distances[cur * (J + 3) + i]); // int d = distances[cur * (J + 3) + i] + jps[i].dist(jps[g]) * 50; // if (md > d) { // md = d; // mi = i; // } // } // ds += distances[cur * (J + 3) + mi]; // visited.set(mi); // tt = moveStraight(cur, mi, tt); // cur = mi; // } // debug(ds, totalCost); // return tt; // } public static final double[] MUL = {0, 0, 0, 1.25, 1.33, 1.4, 1.6, 1.8}; class State { BitSet visited = new BitSet(J + 3); List<Integer> routes = new ArrayList<>(); int dsum; double score; boolean hasScore; State prevCopy; State() { visited.set(J); visited.set(J + 1); visited.set(J + 2); routes.add(J); routes.add(J + 1); routes.add(J + 2); dsum = distances[J][J+1] + distances[J+1][J+2]; } State(State prev) { this.visited = (BitSet)prev.visited.clone(); this.routes = new ArrayList<>(prev.routes); this.dsum = prev.dsum; this.score = prev.score; this.hasScore = true; } State rollback() { return prevCopy; } int neighbor0(double stage) { while (true) { int p; do { p = rand.next(0, J); } while (visited.get(p)); int bi = -1; int bd = iinf; for (int i = 1; i < routes.size(); i++) { int f = routes.get(i - 1); int t = routes.get(i); int diff = distances[f][p] + distances[p][t] - distances[f][t]; if (bd > diff) { bd = diff; bi = i; } } if (bi == -1) { continue; } visited.set(p); dsum += bd; routes.add(bi, p); score = calcScore(0); break; } return 0; } int neighbor1(double stage) { int bd = -iinf; int bp = 0; for (int p = 1; p + 1 < routes.size(); p++) { int f = routes.get(p - 1); int t = routes.get(p + 1); int r = routes.get(p); if (r >= J) { continue; } int diff = distances[f][r] + distances[r][t] - distances[f][t]; if (bd < diff) { bd = diff; bp = p; } } visited.clear(routes.get(bp)); dsum -= bd; routes.remove(bp); score = calcScore(0); return 1; } int neighbor(double stage) { hasScore = false; prevCopy = copy(); if (routes.size() >= 60 && rand.next(3) == 0 || dsum * MUL[D] >= 60 * 1100) { // debug(dsum * MUL[D], getScore(stage), routes.size(), 36000, 1); return neighbor1(stage); } else { // debug(dsum * MUL[D], getScore(stage), routes.size(), 36000, 0); return neighbor0(stage); } } State copy() { return new State(this); } double getScore(double stage) { if (!hasScore) { score = calcScore(stage); hasScore = true; } return score; } double calcScore(double stage) { double score = (routes.size() - 3) * 1800 - dsum * MUL[D]; return score; } long realScore() { int score = 0; return score; } } State annealing(State state, double startTemp, double endTemp, long timeLimit) { State bestState = state.copy(); double bestScore = state.getScore(0); int itr = 0; int rb = 0; int c0 = 0; while (true) { long nowTime = System.currentTimeMillis() - startTime; if (nowTime >= timeLimit) { break; } itr++; double stage = (double)nowTime / timeLimit; double prevScore = state.getScore(stage); double temp = startTemp + (endTemp - startTemp) * nowTime / timeLimit; double thres = prevScore + rand.nextLog() * temp; int nid = state.neighbor(stage); if (nid == -1) { continue; } if (nid == 0) { c0++; } if (bestScore < state.getScore(stage)) { bestScore = state.getScore(stage); bestState = state.copy(); } if (state.getScore(stage) <= thres) { state = state.rollback(); rb++; } } debug(itr, rb, c0); return bestState; } class Result { List<Integer> route; int damage; int time; Pos from; Pos to; public Result(List<Integer> route, int damage, Pos from, Pos to) { this.route = route; this.damage = damage; this.time = route.size() % 60; this.from = from; this.to = to; } public void out(Pos p, int tt) { for (int v : route) { if (v < 4) p = p.moved(v); tt = (tt + 1) % 60; if (beam[tt][p.z]) { totalCost += D; } totalCost++; out.println(ss[v]); } } } Result route(Pos s, Pos g, int tt) { class S { private final Pos p; private final int t; private final int d; public S(Pos p, int t, int d) { this.p = p; this.t = t; this.d = d; } } PriorityQueue<S> queue = new PriorityQueue<>(Comparator.comparingInt(v -> v.d)); queue.add(new S(s, tt, 0)); int[][] dist = new int[60][N * N]; int[][] prev = new int[60][N * N]; for (int i = 0; i < 60; i++) { Arrays.fill(dist[i], iinf); Arrays.fill(prev[i], -1); } dist[tt][s.z] = 0; while (!queue.isEmpty()) { S v = queue.remove(); if (dist[v.t][v.p.z] < v.d) { continue; } if (v.p.z == g.z) { List<Integer> route = new ArrayList<>(); Pos cur = v.p; int ct = v.t; int damage = dist[ct][cur.z]; while (prev[ct][cur.z] != -1) { route.add(prev[ct][cur.z]); if (prev[ct][cur.z] < 4) { cur = cur.moved((prev[ct][cur.z] + 2) % 4); } ct = (ct + 59) % 60; } Collections.reverse(route); return new Result(route, damage + 1, s, g); } int nt = (v.t + 1) % 60; for (int d = 0; d < 4; d++) { Pos q = v.p.moved(d); if (q == null || grid[q.z] == '#') { continue; } int cost = dist[v.t][v.p.z] + 1 + (beam[nt][q.z] ? D : 0); if (dist[nt][q.z] > cost) { dist[nt][q.z] = cost; prev[nt][q.z] = d; queue.add(new S(q, nt, cost)); } } int cost = dist[v.t][v.p.z] + 1 + (beam[nt][v.p.z] ? D : 0); if (dist[nt][v.p.z] > cost) { dist[nt][v.p.z] = cost; prev[nt][v.p.z] = 4; queue.add(new S(v.p, nt, cost)); } } throw new RuntimeException(); } void calcDist(int s) { class S { private final Pos p; private final int d; public S(Pos p, int d) { this.p = p; this.d = d; } } PriorityQueue<S> queue = new PriorityQueue<>(Comparator.comparingInt(v -> v.d)); queue.add(new S(jps[s], 0)); int[] dist = new int[N * N]; Arrays.fill(dist, iinf); dist[jps[s].z] = 0; while (!queue.isEmpty()) { S v = queue.remove(); if (dist[v.p.z] < v.d) { continue; } if (jid[v.p.z] != -1) { distances[s][jid[v.p.z]] = v.d; } for (int d = 0; d < 4; d++) { Pos q = v.p.moved(d); if (q == null || grid[q.z] == '#') { continue; } int cost = dist[v.p.z] + avgWait[q.z]; if (dist[q.z] > cost) { dist[q.z] = cost; queue.add(new S(q, cost)); } } } } void in() { in.nextInt(); D = in.nextInt(); in.nextInt(); grid = new char[N * N]; int jc = 0; for (int i = 0; i < N; i++) { char[] s = in.nextCharArray(); for (int j = 0; j < N; j++) { grid[i * N + j] = s[j]; if (grid[i * N + j] == 'J') { jc++; } } } M = in.nextInt(); J = jc; jps = new Pos[J + 3]; ps = new Pos[M]; ds = new int[M]; for (int i = 0; i < M; i++) { int y = in.nextInt(); int x = in.nextInt(); int d = in.nextInt(); ps[i] = pos(x, y); ds[i] = d; } jc = 0; Arrays.fill(jid, -1); for (int i = 0; i < N * N; i++) { if (grid[i] == 'S') { jps[J] = pos(i); jid[i] = J; grid[i] = '.'; } else if (grid[i] == 'K') { jps[J + 1] = pos(i); jid[i] = J + 1; grid[i] = '.'; } else if (grid[i] == 'G') { jps[J + 2] = pos(i); jid[i] = J + 2; grid[i] = '.'; } else if (grid[i] == 'J') { jid[i] = jc; jps[jc++] = pos(i); } else if (grid[i] == 'E') { grid[i] = '#'; } } } static Pos pos(int x, int y) { return Pos.instances[y * N + x]; } static Pos pos(int z) { return Pos.instances[z]; } static class Timing { Pos p; int t, z; public Timing(Pos p, int t) { this.p = p; this.t = t; this.z = p.z * 60 + t; } } static class Pos implements Comparable<Pos> { static Pos[] instances; static Pos[] moved; static { instances = new Pos[N * N]; moved = new Pos[4 * N * N]; for (int i = 0; i < N * N; i++) { instances[i] = new Pos(i % N, i / N, i); } for (int i = 0; i < N * N; i++) { for (int d = 0; d < 4; d++) { // LURD int nx = i % N + (d - 1) % 2; int ny = i / N + (d - 2) % 2; if (0 <= nx && nx < N && 0 <= ny && ny < N) { moved[i * 4 + d] = instances[ny * N + nx]; } } } } final int x, y, z; private Pos(int x, int y, int z) { this.x = x; this.y = y; this.z = z; } Pos moved(int d) { return moved[z * 4 + d]; } int dist(Pos o) { return Math.abs(x - o.x) + Math.abs(y - o.y); } Pos[] neighbors() { Pos[] p = new Pos[4]; int i = 0; if ((p[i] = moved(0)) != null) i++; if ((p[i] = moved(1)) != null) i++; if ((p[i] = moved(2)) != null) i++; if ((p[i] = moved(3)) != null) i++; return i == 4 ? p : Arrays.copyOf(p, i); } @Override public int compareTo(Pos o) { return Integer.compare(z, o.z); } @Override public boolean equals(Object o) { return o instanceof Pos && z == ((Pos)o).z; } @Override public int hashCode() { return z; } @Override public String toString() { return String.format("(%d, %d)", x, y); } } static void debug(Object... args) { if (!isLocal) { return; } if (args == null || args.getClass() != Object[].class) { args = new Object[] {args}; } System.err.println(Arrays.stream(args).map(obj -> { Class<?> clazz = obj == null ? null : obj.getClass(); return clazz == byte[].class ? Arrays.toString((byte[])obj) : clazz == short[].class ? Arrays.toString((short[])obj) : clazz == int[].class ? Arrays.toString((int[])obj) : clazz == long[].class ? Arrays.toString((long[])obj) : clazz == char[].class ? Arrays.toString((char[])obj) : clazz == float[].class ? Arrays.toString((float[])obj) : clazz == double[].class ? Arrays.toString((double[])obj) : clazz == boolean[].class ? Arrays.toString((boolean[])obj) : obj instanceof Object[] ? Arrays.deepToString((Object[])obj) : String.valueOf(obj); }).collect(Collectors.joining(" "))); } long elapsed() { return (long)((System.currentTimeMillis() - startTime) * (isLocal ? 1.7 : 1)); } boolean elapsed(long timeLimit) { return elapsed() >= timeLimit; } public static void main(String[] args) { new Main().solve(0); } static class Random { private long a, b, c, d; Random() { this(ThreadLocalRandom.current().nextLong()); } Random(long seed) { this.a = seed; for (int i = 0; i < 20; i++) { rand(); } } private int rand() { long t = a ^ (a << 11); a = b; b = c; c = d; d = d ^ (d >>> 19) ^ t ^ (t >>> 8); return (int)(a & 0x7fffffff); } long next() { return (long)rand() << 31 | rand(); } int next(int n) { return rand() % n; } int next(int l, int r) { return rand() % (r - l) + l; } double nextDouble() { return rand() / 2147483648.0; } double nextLog() { return Math.log(rand() + 1) - 21.487562597358306; } } static class In { private final BufferedReader reader; private StringTokenizer tokenizer; In(InputStream input) { this.reader = new BufferedReader(new InputStreamReader(input), 0x10000); } String next() { try { while (tokenizer == null || !tokenizer.hasMoreTokens()) { tokenizer = new StringTokenizer(reader.readLine()); } } catch (IOException ignored) { } return tokenizer.nextToken(); } int nextInt() { return Integer.parseInt(next()); } long nextLong() { return Long.parseLong(next()); } double nextDouble() { return Double.parseDouble(next()); } char[] nextCharArray() { return next().toCharArray(); } String[] nextStringArray(int n) { String[] s = new String[n]; for (int i = 0; i < n; i++) { s[i] = next(); } return s; } char[][] nextCharGrid(int n, int m) { char[][] a = new char[n][m]; for (int i = 0; i < n; i++) { a[i] = next().toCharArray(); } return a; } int[] nextIntArray(int n) { int[] a = new int[n]; for (int i = 0; i < n; i++) { a[i] = nextInt(); } return a; } int[] nextIntArray(int n, IntUnaryOperator op) { int[] a = new int[n]; for (int i = 0; i < n; i++) { a[i] = op.applyAsInt(nextInt()); } return a; } int[][] nextIntMatrix(int h, int w) { int[][] a = new int[h][w]; for (int i = 0; i < h; i++) { a[i] = nextIntArray(w); } return a; } long[] nextLongArray(int n) { long[] a = new long[n]; for (int i = 0; i < n; i++) { a[i] = nextLong(); } return a; } long[] nextLongArray(int n, LongUnaryOperator op) { long[] a = new long[n]; for (int i = 0; i < n; i++) { a[i] = op.applyAsLong(nextLong()); } return a; } long[][] nextLongMatrix(int h, int w) { long[][] a = new long[h][w]; for (int i = 0; i < h; i++) { a[i] = nextLongArray(w); } return a; } List<List<Integer>> nextEdges(int n, int m, boolean directed) { List<List<Integer>> res = new ArrayList<>(); for (int i = 0; i < n; i++) { res.add(new ArrayList<>()); } for (int i = 0; i < m; i++) { int u = nextInt() - 1; int v = nextInt() - 1; res.get(u).add(v); if (!directed) { res.get(v).add(u); } } return res; } } }