提出 #69481066
ソースコード 拡げる
using System;
using System.Collections.Generic;
using System.Diagnostics;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
using System.Numerics;
using System.IO.Pipes;
using System.Diagnostics.CodeAnalysis;
using System.Runtime.Versioning;
using System.CodeDom;
namespace AtCoder.Abc
{
public class AtCoderABC
{
public static void Main(string[] args)
{
var sw = new System.IO.StreamWriter(Console.OpenStandardOutput()) { AutoFlush = false };
Console.SetOut(sw);
// 実行したいクラスのMainメソッドを呼び出す
// QuestionA.Run();
// QuestionB.Run();
QuestionC.Run();
// QuestionD.Run();
// QuestionE.Run();
// QuestionF.Run();
// QuestionG.Run();
// QuestionH.Run();
// QuestionI.Run();
Console.Out.Flush();
}
}
public class QuestionA
{
public static void Run()
{
var LA = Utilities.GetLongArray();
var A = LA[0];
var B = LA[1];
var C = LA[2];
var HS = new HashSet<long>();
HS.Add(A);
HS.Add(B);
HS.Add(C);
if (HS.Count != 3)
{
Console.WriteLine("Yes");
}
else
{
Console.WriteLine("No");
}
}
}
public class QuestionB
{
public static void Run()
{
var LA = Utilities.GetLongArray();
var N = LA[0];
var M = LA[1];
var K = LA[2];
var LST = new List<long>[N];
for (int i = 0; i < N; ++i)
{
LST[i] = new List<long>();
}
var ANS = new List<long>();
for (int i = 0; i < K; ++i)
{
LA = Utilities.GetLongArray();
var A = LA[0];
var B = LA[1];
LST[A - 1].Add(B);
if (LST[A-1].Count == M)
{
ANS.Add(A - 1);
}
}
int cnt = 0;
foreach (var i in ANS)
{
if (cnt != 0) Console.Write(" ");
Console.Write(i+1);
cnt++;
}
Console.WriteLine("");
}
}
public class QuestionC
{
public static void Run()
{
var LA = Utilities.GetLongArray();
var N = LA[0];
var GET = new bool[N];
for (int i =0; i < N; ++i)
{
GET[i] = false;
}
var MAP = new Dictionary<long, List<long>>();
for (int i = 0; i < N; ++i)
{
var LST = new List<long>();
MAP.Add(i, LST);
}
Queue<long> q = new Queue<long>();
var ANS = new HashSet<long>();
for (int i = 0; i < N; ++i)
{
LA = Utilities.GetLongArray();
var A = LA[0];
var B = LA[1];
if (A == 0 && B == 0)
{
GET[i] = true;
q.Enqueue(i);
ANS.Add(i);
}
else
{
MAP[A-1].Add(i);
MAP[B-1].Add(i);
}
}
while (q.Count() != 0)
{
long v = q.Dequeue();
long num = MAP[v].Count();
for (int i = 0; i < num; ++i)
{
long next_v = MAP[v][i];
if (GET[next_v] == false)
{
GET[next_v] = true;
q.Enqueue(next_v);
ANS.Add(next_v);
}
else
{
continue;
}
}
}
Console.WriteLine(ANS.Count);
}
}
public class QuestionD
{
public static void Run()
{
var LA = Utilities.GetLongArray();
}
}
public class QuestionE
{
public static void Run()
{
var LA = Utilities.GetLongArray();
}
}
public class QuestionF
{
public static void Run()
{
var LA = Utilities.GetLongArray();
}
}
public class QuestionG
{
public static void Run()
{
var LA = Utilities.GetLongArray();
}
}
public class QuestionH
{
public static void Run()
{
var LA = Utilities.GetLongArray();
}
}
public class QuestionI
{
public static void Run()
{
var LA = Utilities.GetLongArray();
}
}
internal class Utilities
{
public static string GetString()
{
return Console.ReadLine();
}
public static long GetLong()
{
return long.Parse(Console.ReadLine());
}
public static string[] GetStringArray()
{
return Console.ReadLine().Split(' ');
}
public static long[] GetLongArray()
{
return Console.ReadLine().Split(' ').Select(i => long.Parse(i)).ToArray();
}
public static void PrintArray(long[] array)
{
foreach (var item in array)
{
Console.WriteLine(item);
}
}
public static void PrintDouble(double d)
{
Console.WriteLine(string.Format("{0:f12}", d));
}
}
internal class Library
{
// Gcd（最大公約数）
public static long Gcd(long m, long n)
{
if (n == 0) return m;
return Gcd(n, m % n);
}
// Lcm（最小公倍数）答えが 10^18を超えるとき -1 を返す
public static long Lcm(long a, long b)
{
long POW18 = 1000000000000000000;
long r = a / Gcd(a, b);
if (r > (POW18 / b))
return -1;
else
return (r * b);
}
public static long Mod = 1000000007;
public static long ModPow(long a, long n)
{
long res = 1;
while (n > 0)
{
if ((n & 1) == 1)
{
res = res * a % Mod;
}
a = a * a % Mod;
n >>= 1;
}
return res;
}
public static long ModInv(long a)
{
return ModPow(a, Mod - 2);
}
public static long ModDiv(long a, long b)
{
return a * ModInv(b) % Mod;
}
public static long ModAdd(long a, long b)
{
return (a + b) % Mod;
}
public static long ModSub(long a, long b)
{
return (a - b + Mod) % Mod;
}
public static long ModMul(long a, long b)
{
return a * b % Mod;
}
public static long ModFact(long n)
{
long res = 1;
for (long i = 1; i <= n; i++)
{
res = res * i % Mod;
}
return res;
}
public static long ModComb(long n, long k)
{
if (n < k) return 0;
if (n < 0 || k < 0) return 0;
return ModFact(n) * ModInv(ModFact(k)) % Mod * ModInv(ModFact(n - k)) % Mod;
}
public static long ModPerm(long n, long k)
{
if (n < k) return 0;
if (n < 0 || k < 0) return 0;
return ModFact(n) * ModInv(ModFact(n - k)) % Mod;
}
// ダイクストラ法
// 使用例:
//int n = 5; // ノード数
//var graph = new List<(int to, long cost)>[n];
// for (int i = 0; i<n; i++)
// {
// graph[i] = new List<(int to, long cost)>();
// }
// エッジの追加 (例: ノード0からノード1へのコスト10のエッジ)
//graph[0].Add((1, 10));
//graph[0].Add((2, 3));
//graph[1].Add((2, 1));
//graph[1].Add((3, 2));
//graph[2].Add((1, 4));
//graph[2].Add((3, 8));
//graph[2].Add((4, 2));
//graph[3].Add((4, 7));
//graph[4].Add((3, 9));
// ダイクストラ法の呼び出し
//int startNode = 0; // 開始ノード
//var distances = Library.Dijkstra(n, graph, startNode);
// 結果の表示
//for (int i = 0; i<n; i++)
//{
//Console.WriteLine($"Node {i}: {distances[i]}");
//}
public static long[] Dijkstra(int n, List<(int to, long cost)>[] graph, int start)
{
var dist = new long[n];
for (int i = 0; i < n; i++) dist[i] = long.MaxValue;
dist[start] = 0;
var pq = new PriorityQueue<(long dist, int node)>();
pq.Enqueue((0, start));
while (pq.Count > 0)
{
var (d, v) = pq.Dequeue();
if (dist[v] < d) continue;
foreach (var (to, cost) in graph[v])
{
var newDist = d + cost;
if (newDist < dist[to])
{
dist[to] = newDist;
pq.Enqueue((newDist, to));
}
}
}
return dist;
}
// 優先度付きキューの実装
public class PriorityQueue<T> where T : IComparable<T>
{
private List<T> data;
public PriorityQueue()
{
this.data = new List<T>();
}
public void Enqueue(T item)
{
data.Add(item);
int ci = data.Count - 1;
while (ci > 0)
{
int pi = (ci - 1) / 2;
if (data[ci].CompareTo(data[pi]) >= 0) break;
var tmp = data[ci];
data[ci] = data[pi];
data[pi] = tmp;
ci = pi;
}
}
public T Dequeue()
{
int li = data.Count - 1;
var frontItem = data[0];
data[0] = data[li];
data.RemoveAt(li);
--li;
int pi = 0;
while (true)
{
int ci = pi * 2 + 1;
if (ci > li) break;
int rc = ci + 1;
if (rc <= li && data[rc].CompareTo(data[ci]) < 0)
ci = rc;
if (data[pi].CompareTo(data[ci]) <= 0) break;
var tmp = data[pi];
data[pi] = data[ci];
data[ci] = tmp;
pi = ci;
}
return frontItem;
}
public int Count => data.Count;
}
// Union-Find Treeの実装
public class UnionFind
{
private int[] parent;
private int[] rank;
private int[] size;
public UnionFind(int n)
{
parent = new int[n];
rank = new int[n];
size = new int[n];
for (int i = 0; i < n; i++)
{
parent[i] = i;
rank[i] = 0;
size[i] = 1;
}
}
public int Find(int x)
{
if (parent[x] == x)
{
return x;
}
else
{
parent[x] = Find(parent[x]);
return parent[x];
}
}
public void Union(int x, int y)
{
int rootX = Find(x);
int rootY = Find(y);
if (rootX != rootY)
{
if (rank[rootX] < rank[rootY])
{
parent[rootX] = rootY;
size[rootY] += size[rootX];
}
else if (rank[rootX] > rank[rootY])
{
parent[rootY] = rootX;
size[rootX] += size[rootY];
}
else
{
parent[rootY] = rootX;
size[rootX] += size[rootY];
rank[rootX]++;
}
}
}
public bool Same(int x, int y)
{
return Find(x) == Find(y);
}
public int Size(int x)
{
return size[Find(x)];
}
public int CountGroups()
{
int count = 0;
for (int i = 0; i < parent.Length; i++)
{
if (parent[i] == i)
{
count++;
}
}
return count;
}
}
}
}
提出情報
ジャッジ結果
| セット名 |
Sample |
All |
| 得点 / 配点 |
0 / 0 |
300 / 300 |
| 結果 |
|
|
| セット名 |
テストケース |
| Sample |
sample_01.txt, sample_02.txt |
| All |
hand_01.txt, hand_02.txt, random_01.txt, random_02.txt, random_03.txt, random_04.txt, random_05.txt, random_06.txt, random_07.txt, random_08.txt, random_09.txt, random_10.txt, random_11.txt, random_12.txt, random_13.txt, random_14.txt, random_15.txt, random_16.txt, random_17.txt, random_18.txt, random_19.txt, random_20.txt, random_21.txt, random_22.txt, random_23.txt, random_24.txt, random_25.txt, random_26.txt, sample_01.txt, sample_02.txt |
| ケース名 |
結果 |
実行時間 |
メモリ |
| hand_01.txt |
AC |
55 ms |
26580 KiB |
| hand_02.txt |
AC |
52 ms |
26636 KiB |
| random_01.txt |
AC |
306 ms |
84108 KiB |
| random_02.txt |
AC |
68 ms |
31152 KiB |
| random_03.txt |
AC |
383 ms |
89052 KiB |
| random_04.txt |
AC |
284 ms |
76240 KiB |
| random_05.txt |
AC |
410 ms |
89024 KiB |
| random_06.txt |
AC |
288 ms |
77024 KiB |
| random_07.txt |
AC |
397 ms |
88860 KiB |
| random_08.txt |
AC |
154 ms |
82852 KiB |
| random_09.txt |
AC |
373 ms |
87176 KiB |
| random_10.txt |
AC |
415 ms |
85104 KiB |
| random_11.txt |
AC |
222 ms |
87312 KiB |
| random_12.txt |
AC |
368 ms |
88044 KiB |
| random_13.txt |
AC |
402 ms |
88200 KiB |
| random_14.txt |
AC |
396 ms |
88048 KiB |
| random_15.txt |
AC |
414 ms |
88388 KiB |
| random_16.txt |
AC |
157 ms |
66452 KiB |
| random_17.txt |
AC |
312 ms |
85292 KiB |
| random_18.txt |
AC |
73 ms |
36160 KiB |
| random_19.txt |
AC |
190 ms |
70476 KiB |
| random_20.txt |
AC |
257 ms |
72892 KiB |
| random_21.txt |
AC |
52 ms |
27764 KiB |
| random_22.txt |
AC |
96 ms |
45972 KiB |
| random_23.txt |
AC |
296 ms |
81424 KiB |
| random_24.txt |
AC |
106 ms |
49292 KiB |
| random_25.txt |
AC |
183 ms |
70508 KiB |
| random_26.txt |
AC |
68 ms |
31864 KiB |
| sample_01.txt |
AC |
56 ms |
26448 KiB |
| sample_02.txt |
AC |
49 ms |
26556 KiB |