Submission #1416902
Source Code Expand
using System; using System.Collections; using System.Collections.Generic; using System.Linq; using System.IO; using System.Text; using System.Globalization; using System.Diagnostics; class Myon { public Myon() { } public static int Main() { new Myon().calc(); return 0; } Scanner cin; List<Tuple<int, int>>[] es; int[] loop; int[] memo; List<int> A; List<int> B; int[] Asum; int[] Bsum; void calc() { cin = new Scanner(); int N = cin.nextInt(); int M = cin.nextInt(); int K = cin.nextInt(); init(N); es = new List<Tuple<int, int>>[N]; for (int i = 0; i < N; i++) { es[i] = new List<Tuple<int, int>>(); } for (int i = 0; i < M; i++) { int f = cin.nextInt() - 1; int t = cin.nextInt() - 1; int c = cin.nextInt(); es[f].Add(Tuple.Create(t, c)); es[t].Add(Tuple.Create(f, c)); connect(f, t); } loop = new int[N]; memo = new int[N]; for (int i = 0; i < N; i++) { if (uni[i] < 0) findLoop(i, -1); } A = new List<int>(); B = new List<int>(); for (int i = 0; i < N; i++) { foreach (var e in es[i]) { int j = e.Item1; if (i > j) continue; if(loop[i] == 1 && loop[j] == 1) { B.Add(e.Item2); } else { A.Add(e.Item2); } } } A.Sort(); B.Sort(); Asum = new int[A.Count + 1]; Bsum = new int[B.Count + 1]; for (int i = 0; i < A.Count; i++) { Asum[i + 1] = Asum[i] + A[i]; } for (int i = 0; i < B.Count; i++) { Bsum[i + 1] = Bsum[i] + B[i]; } int cnt = 0; for (int i = 0; i < N; i++) { if (uni[i] < 0) cnt++; } int need = K - cnt; if (need < 0) need = 0; long ans = long.MaxValue / 2; if (A.Count >= need) ans = Asum[need]; for (int i = 0; i <= need; i++) { int j = need - i + 1; if (Asum.Length <= i) continue; if (Bsum.Length <= j) continue; ans = Math.Min(Asum[i] + Bsum[j], ans); } Console.WriteLine(ans); } int[] uni; void init(int N) { uni = new int[N]; for (int i = 0; i < N; i++) { uni[i] = -1; } } int root(int a) { if (uni[a] < 0) return a; else return uni[a] = root(uni[a]); } bool connect(int a, int b) { a = root(a); b = root(b); if (a == b) return false; if (uni[a] > uni[b]) swap(ref a, ref b); uni[a] += uni[b]; uni[b] = a; return true; } void swap<T>(ref T a, ref T b) { T c = a; a = b; b = c; } int findLoop(int now, int pre) { if(memo[now] == 1) { loop[now] = 1; return 1; } memo[now] = 1; foreach (var e in es[now]) { int next = e.Item1; if (next == pre) continue; int ans = findLoop(next, now); if(ans == 1) { if (loop[now] == 1) return 2; loop[now] = 1; return 1; } if (ans == 2) return 2; } memo[now] = 0; return 0; } } class Scanner { string[] s; int i; char[] cs = new char[] { ' ' }; public Scanner() { s = new string[0]; i = 0; } public string next() { if (i < s.Length) return s[i++]; string st = Console.ReadLine(); while (st == "") st = Console.ReadLine(); s = st.Split(cs, StringSplitOptions.RemoveEmptyEntries); i = 0; return s[i++]; } public int nextInt() { return int.Parse(next()); } public long nextLong() { return long.Parse(next()); } public double nextDouble() { return double.Parse(next()); } }
Submission Info
Submission Time | |
---|---|
Task | E - 独立記念日 |
User | chokudai |
Language | C# (Mono 4.6.2.0) |
Score | 100 |
Code Size | 4572 Byte |
Status | AC |
Exec Time | 24 ms |
Memory | 13396 KB |
Judge Result
Set Name | nonloop | loop | ||||
---|---|---|---|---|---|---|
Score / Max Score | 30 / 30 | 70 / 70 | ||||
Status |
|
|
Set Name | Test Cases |
---|---|
nonloop | nonloop/case_000.txt, nonloop/case_001.txt, nonloop/case_002.txt, nonloop/case_003.txt, nonloop/case_004.txt, nonloop/case_005.txt, nonloop/case_006.txt, nonloop/case_007.txt, nonloop/case_008.txt, nonloop/case_009.txt, nonloop/case_010.txt, nonloop/case_011.txt, nonloop/case_012.txt, nonloop/case_013.txt, nonloop/case_014.txt, nonloop/case_015.txt, nonloop/case_016.txt, nonloop/case_017.txt, nonloop/case_018.txt, nonloop/case_019.txt, nonloop/case_020.txt, nonloop/case_021.txt, nonloop/case_022.txt, nonloop/case_023.txt, nonloop/case_024.txt, nonloop/case_025.txt, nonloop/case_026.txt, nonloop/case_027.txt, nonloop/case_028.txt, nonloop/case_029.txt, nonloop/case_030.txt, nonloop/case_031.txt, nonloop/case_032.txt, nonloop/case_033.txt |
loop | loop/case_000.txt, loop/case_001.txt, loop/case_002.txt, loop/case_003.txt, loop/case_004.txt, loop/case_005.txt, loop/case_006.txt, loop/case_007.txt, loop/case_008.txt, loop/case_009.txt, loop/case_010.txt, loop/case_011.txt, loop/case_012.txt, loop/case_013.txt, loop/case_014.txt, loop/case_015.txt, loop/case_016.txt, loop/case_017.txt, loop/case_018.txt, loop/case_019.txt, loop/case_020.txt, loop/case_021.txt, loop/case_022.txt, loop/case_023.txt, loop/case_024.txt, loop/case_025.txt, loop/case_026.txt, loop/case_027.txt, loop/case_028.txt, loop/case_029.txt, loop/case_030.txt, loop/case_031.txt, loop/case_032.txt, loop/case_033.txt, loop/loop_case_000.txt, loop/loop_case_001.txt, loop/loop_case_002.txt, loop/loop_case_003.txt, loop/loop_case_004.txt, loop/loop_case_005.txt, loop/loop_case_006.txt, loop/loop_case_007.txt, loop/loop_case_008.txt, loop/loop_case_009.txt, loop/loop_case_010.txt, loop/loop_case_011.txt, loop/loop_case_012.txt, loop/loop_case_013.txt, loop/loop_case_014.txt, loop/loop_case_015.txt, loop/loop_case_016.txt, loop/loop_case_017.txt, loop/loop_case_018.txt, loop/loop_case_019.txt, loop/loop_case_020.txt, loop/loop_case_021.txt, loop/loop_case_022.txt, loop/loop_case_023.txt, loop/loop_case_024.txt, loop/loop_case_025.txt, loop/loop_case_026.txt, loop/loop_case_027.txt, loop/loop_case_028.txt, loop/loop_case_029.txt, loop/loop_case_030.txt, loop/loop_case_031.txt |
Case Name | Status | Exec Time | Memory |
---|---|---|---|
loop/case_000.txt | AC | 23 ms | 9300 KB |
loop/case_001.txt | AC | 23 ms | 11348 KB |
loop/case_002.txt | AC | 23 ms | 11348 KB |
loop/case_003.txt | AC | 23 ms | 11348 KB |
loop/case_004.txt | AC | 23 ms | 9300 KB |
loop/case_005.txt | AC | 23 ms | 11348 KB |
loop/case_006.txt | AC | 23 ms | 13268 KB |
loop/case_007.txt | AC | 22 ms | 9172 KB |
loop/case_008.txt | AC | 23 ms | 11220 KB |
loop/case_009.txt | AC | 23 ms | 13268 KB |
loop/case_010.txt | AC | 23 ms | 11348 KB |
loop/case_011.txt | AC | 24 ms | 13396 KB |
loop/case_012.txt | AC | 23 ms | 11348 KB |
loop/case_013.txt | AC | 23 ms | 11348 KB |
loop/case_014.txt | AC | 23 ms | 11348 KB |
loop/case_015.txt | AC | 23 ms | 9300 KB |
loop/case_016.txt | AC | 24 ms | 11348 KB |
loop/case_017.txt | AC | 24 ms | 13396 KB |
loop/case_018.txt | AC | 23 ms | 9300 KB |
loop/case_019.txt | AC | 24 ms | 11348 KB |
loop/case_020.txt | AC | 24 ms | 11348 KB |
loop/case_021.txt | AC | 23 ms | 11348 KB |
loop/case_022.txt | AC | 23 ms | 11348 KB |
loop/case_023.txt | AC | 23 ms | 11348 KB |
loop/case_024.txt | AC | 23 ms | 9300 KB |
loop/case_025.txt | AC | 24 ms | 11348 KB |
loop/case_026.txt | AC | 23 ms | 9300 KB |
loop/case_027.txt | AC | 24 ms | 11348 KB |
loop/case_028.txt | AC | 23 ms | 9300 KB |
loop/case_029.txt | AC | 23 ms | 11348 KB |
loop/case_030.txt | AC | 24 ms | 11348 KB |
loop/case_031.txt | AC | 23 ms | 11348 KB |
loop/case_032.txt | AC | 24 ms | 11220 KB |
loop/case_033.txt | AC | 24 ms | 11348 KB |
loop/loop_case_000.txt | AC | 24 ms | 13396 KB |
loop/loop_case_001.txt | AC | 23 ms | 9300 KB |
loop/loop_case_002.txt | AC | 23 ms | 9300 KB |
loop/loop_case_003.txt | AC | 23 ms | 11348 KB |
loop/loop_case_004.txt | AC | 24 ms | 11348 KB |
loop/loop_case_005.txt | AC | 23 ms | 9300 KB |
loop/loop_case_006.txt | AC | 23 ms | 9300 KB |
loop/loop_case_007.txt | AC | 23 ms | 9172 KB |
loop/loop_case_008.txt | AC | 23 ms | 11348 KB |
loop/loop_case_009.txt | AC | 23 ms | 11348 KB |
loop/loop_case_010.txt | AC | 24 ms | 11348 KB |
loop/loop_case_011.txt | AC | 23 ms | 9300 KB |
loop/loop_case_012.txt | AC | 24 ms | 11348 KB |
loop/loop_case_013.txt | AC | 24 ms | 11348 KB |
loop/loop_case_014.txt | AC | 24 ms | 11348 KB |
loop/loop_case_015.txt | AC | 23 ms | 11348 KB |
loop/loop_case_016.txt | AC | 24 ms | 13396 KB |
loop/loop_case_017.txt | AC | 23 ms | 9300 KB |
loop/loop_case_018.txt | AC | 23 ms | 9300 KB |
loop/loop_case_019.txt | AC | 24 ms | 11348 KB |
loop/loop_case_020.txt | AC | 23 ms | 11348 KB |
loop/loop_case_021.txt | AC | 23 ms | 11348 KB |
loop/loop_case_022.txt | AC | 24 ms | 11348 KB |
loop/loop_case_023.txt | AC | 24 ms | 11348 KB |
loop/loop_case_024.txt | AC | 23 ms | 9300 KB |
loop/loop_case_025.txt | AC | 23 ms | 11348 KB |
loop/loop_case_026.txt | AC | 23 ms | 11348 KB |
loop/loop_case_027.txt | AC | 24 ms | 13396 KB |
loop/loop_case_028.txt | AC | 23 ms | 11220 KB |
loop/loop_case_029.txt | AC | 24 ms | 13396 KB |
loop/loop_case_030.txt | AC | 23 ms | 11348 KB |
loop/loop_case_031.txt | AC | 24 ms | 11348 KB |
nonloop/case_000.txt | AC | 24 ms | 13396 KB |
nonloop/case_001.txt | AC | 24 ms | 13396 KB |
nonloop/case_002.txt | AC | 24 ms | 11348 KB |
nonloop/case_003.txt | AC | 23 ms | 11348 KB |
nonloop/case_004.txt | AC | 23 ms | 11348 KB |
nonloop/case_005.txt | AC | 24 ms | 11348 KB |
nonloop/case_006.txt | AC | 23 ms | 11220 KB |
nonloop/case_007.txt | AC | 23 ms | 11220 KB |
nonloop/case_008.txt | AC | 23 ms | 11220 KB |
nonloop/case_009.txt | AC | 23 ms | 13268 KB |
nonloop/case_010.txt | AC | 23 ms | 9300 KB |
nonloop/case_011.txt | AC | 24 ms | 13396 KB |
nonloop/case_012.txt | AC | 23 ms | 9300 KB |
nonloop/case_013.txt | AC | 24 ms | 13396 KB |
nonloop/case_014.txt | AC | 24 ms | 13396 KB |
nonloop/case_015.txt | AC | 23 ms | 11348 KB |
nonloop/case_016.txt | AC | 24 ms | 11348 KB |
nonloop/case_017.txt | AC | 23 ms | 11348 KB |
nonloop/case_018.txt | AC | 24 ms | 11348 KB |
nonloop/case_019.txt | AC | 23 ms | 9300 KB |
nonloop/case_020.txt | AC | 24 ms | 13396 KB |
nonloop/case_021.txt | AC | 24 ms | 13396 KB |
nonloop/case_022.txt | AC | 24 ms | 11348 KB |
nonloop/case_023.txt | AC | 24 ms | 11348 KB |
nonloop/case_024.txt | AC | 24 ms | 11348 KB |
nonloop/case_025.txt | AC | 23 ms | 11348 KB |
nonloop/case_026.txt | AC | 24 ms | 11348 KB |
nonloop/case_027.txt | AC | 24 ms | 11348 KB |
nonloop/case_028.txt | AC | 24 ms | 11348 KB |
nonloop/case_029.txt | AC | 24 ms | 13396 KB |
nonloop/case_030.txt | AC | 24 ms | 13396 KB |
nonloop/case_031.txt | AC | 23 ms | 11348 KB |
nonloop/case_032.txt | AC | 23 ms | 9300 KB |
nonloop/case_033.txt | AC | 23 ms | 11348 KB |