結果
問題 | No.1582 Vertexes vs Edges |
ユーザー | cyclerecycle9 |
提出日時 | 2021-09-10 21:49:46 |
言語 | Java21 (openjdk 21) |
結果 |
AC
|
実行時間 | 219 ms / 2,000 ms |
コード長 | 4,620 bytes |
コンパイル時間 | 5,096 ms |
コンパイル使用メモリ | 77,232 KB |
実行使用メモリ | 66,984 KB |
最終ジャッジ日時 | 2023-09-02 16:53:11 |
合計ジャッジ時間 | 12,889 ms |
ジャッジサーバーID (参考情報) |
judge14 / judge13 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 44 ms
49,532 KB |
testcase_01 | AC | 44 ms
49,428 KB |
testcase_02 | AC | 46 ms
49,728 KB |
testcase_03 | AC | 45 ms
49,440 KB |
testcase_04 | AC | 62 ms
50,088 KB |
testcase_05 | AC | 168 ms
66,532 KB |
testcase_06 | AC | 77 ms
51,512 KB |
testcase_07 | AC | 87 ms
54,364 KB |
testcase_08 | AC | 128 ms
61,508 KB |
testcase_09 | AC | 170 ms
66,616 KB |
testcase_10 | AC | 137 ms
61,656 KB |
testcase_11 | AC | 78 ms
52,380 KB |
testcase_12 | AC | 117 ms
57,024 KB |
testcase_13 | AC | 143 ms
61,868 KB |
testcase_14 | AC | 161 ms
61,696 KB |
testcase_15 | AC | 188 ms
66,084 KB |
testcase_16 | AC | 136 ms
57,764 KB |
testcase_17 | AC | 148 ms
62,084 KB |
testcase_18 | AC | 184 ms
66,088 KB |
testcase_19 | AC | 144 ms
61,884 KB |
testcase_20 | AC | 155 ms
61,728 KB |
testcase_21 | AC | 143 ms
61,752 KB |
testcase_22 | AC | 185 ms
66,156 KB |
testcase_23 | AC | 138 ms
57,248 KB |
testcase_24 | AC | 102 ms
53,572 KB |
testcase_25 | AC | 156 ms
62,400 KB |
testcase_26 | AC | 131 ms
57,704 KB |
testcase_27 | AC | 207 ms
65,916 KB |
testcase_28 | AC | 119 ms
57,220 KB |
testcase_29 | AC | 161 ms
61,992 KB |
testcase_30 | AC | 140 ms
61,820 KB |
testcase_31 | AC | 164 ms
62,036 KB |
testcase_32 | AC | 132 ms
59,036 KB |
testcase_33 | AC | 217 ms
66,984 KB |
testcase_34 | AC | 218 ms
66,580 KB |
testcase_35 | AC | 219 ms
64,828 KB |
testcase_36 | AC | 46 ms
49,412 KB |
testcase_37 | AC | 45 ms
49,728 KB |
testcase_38 | AC | 45 ms
49,816 KB |
ソースコード
import java.io.IOException; import java.io.InputStream; import java.io.PrintWriter; import java.math.BigDecimal; import java.math.RoundingMode; import java.util.*; public class Main { static final long MOD1=1000000007; static final long MOD=998244353; static int ans=0; public static void main(String[] args){ PrintWriter out = new PrintWriter(System.out); InputReader sc=new InputReader(System.in); int N = sc.nextInt(); graph G = new graph(N); for (int i = 0; i < N - 1; i++) { int a = sc.nextInt()-1; int b = sc.nextInt()-1; G.addEdge(a, b, 1); G.addEdge(b, a, 1); } int[][] dp = new int[N][2]; G.dfs(0, -1, dp); System.out.println(N - Math.max(dp[0][0], dp[0][1])); } static class Edge implements Comparable<Edge>{ int to; long v; public Edge(int to,long v) { this.to=to; this.v=v; } @Override public boolean equals(Object obj){ if(obj instanceof Edge) { Edge other = (Edge) obj; return other.to==this.to && other.v==this.v; } return false; }//同値の定義 @Override public int hashCode() { return Objects.hash(this.to,this.v); } @Override public int compareTo( Edge p2 ){ if (this.v>p2.v) { return 1; } else if (this.v<p2.v) { return -1; } else { return 0; } } } static class graph{ ArrayList<Edge>[] list; int size; long INF=Long.MAX_VALUE/2; int[] color; @SuppressWarnings("unchecked") public graph(int n) { size = n; list = new ArrayList[n]; color =new int[n]; for(int i=0;i<n;i++){ list[i] = new ArrayList<Edge>(); } } void addEdge(int from,int to,long w) { list[from].add(new Edge(to,w)); } void dfs(int v, int p, int[][] dp) { dp[v][0] = 1; for (Edge e: list[v]) { if (e.to==p)continue; dfs(e.to, v, dp); dp[v][0] += dp[e.to][1]; dp[v][1] += Math.max(dp[e.to][0], dp[e.to][1]); } } } static class InputReader { private InputStream in; private byte[] buffer = new byte[1024]; private int curbuf; private int lenbuf; public InputReader(InputStream in) { this.in = in; this.curbuf = this.lenbuf = 0; } public boolean hasNextByte() { if (curbuf >= lenbuf) { curbuf = 0; try { lenbuf = in.read(buffer); } catch (IOException e) { throw new InputMismatchException(); } if (lenbuf <= 0) return false; } return true; } private int readByte() { if (hasNextByte()) return buffer[curbuf++]; else return -1; } private boolean isSpaceChar(int c) { return !(c >= 33 && c <= 126); } private void skip() { while (hasNextByte() && isSpaceChar(buffer[curbuf])) curbuf++; } public boolean hasNext() { skip(); return hasNextByte(); } public String next() { if (!hasNext()) throw new NoSuchElementException(); StringBuilder sb = new StringBuilder(); int b = readByte(); while (!isSpaceChar(b)) { sb.appendCodePoint(b); b = readByte(); } return sb.toString(); } public int nextInt() { if (!hasNext()) throw new NoSuchElementException(); int c = readByte(); while (isSpaceChar(c)) c = readByte(); boolean minus = false; if (c == '-') { minus = true; c = readByte(); } int res = 0; do { if (c < '0' || c > '9') throw new InputMismatchException(); res = res * 10 + c - '0'; c = readByte(); } while (!isSpaceChar(c)); return (minus) ? -res : res; } public long nextLong() { if (!hasNext()) throw new NoSuchElementException(); int c = readByte(); while (isSpaceChar(c)) c = readByte(); boolean minus = false; if (c == '-') { minus = true; c = readByte(); } long res = 0; do { if (c < '0' || c > '9') throw new InputMismatchException(); res = res * 10 + c - '0'; c = readByte(); } while (!isSpaceChar(c)); return (minus) ? -res : res; } public double nextDouble() { return Double.parseDouble(next()); } public int[] nextIntArray(int n) { int[] a = new int[n]; for (int i = 0; i < n; i++) a[i] = nextInt(); return a; } public double[] nextDoubleArray(int n) { double[] a = new double[n]; for (int i = 0; i < n; i++) a[i] = nextDouble(); return a; } public long[] nextLongArray(int n) { long[] a = new long[n]; for (int i = 0; i < n; i++) a[i] = nextLong(); return a; } public char[][] nextCharMap(int n, int m) { char[][] map = new char[n][m]; for (int i = 0; i < n; i++) map[i] = next().toCharArray(); return map; } } }