Submission #992607


Source Code Expand

using System;
using System.Text;
using System.Collections.Generic;
class Solve{
    int N,M;
    List<int>[] L;
    public Solve(){}
    StringBuilder sb;
    public static int Main(){
        new Solve().Run();
        return 0;
    }
    void Run(){
        sb = new StringBuilder();
        Read();
        Calc();
        Console.Write(sb.ToString());
    }
    void Calc(){
        UnionFind U = new UnionFind(N);
        for(int i=0;i<M;i++){
            for(int j=0;j<L[i].Count-1;j++){
                U.Union(L[i][j],L[i][j+1]);
            }
        }
        if(U.Num(0) == N){
            sb.Append("YES\n");
        }
        else{
            sb.Append("NO\n");
        }
    }
    void Read(){
        string[] str = Console.ReadLine().Split(' ');
        N = int.Parse(str[0]);
        M = int.Parse(str[1]);
        L = new List<int>[M];
        for(int i=0;i<M;i++){
            L[i] = new List<int>();
        }
        for(int i=0;i<N;i++){
            str = Console.ReadLine().Split(' ');
            int k = int.Parse(str[0]);
            for(int j=1;j<=k;j++){
                L[int.Parse(str[j])-1].Add(i);
            }
        }
    }    
}
class UnionFind{
    int[] par;
    int[] num;
    public UnionFind(int n){
        par = new int[n];
        num = new int[n];
        for(int i=0;i<n;i++){
            par[i] = i;
            num[i] = 1;
        }
    }
    public int Num(int x){
        return num[Get(x)];
    }
    public void Union(int x,int y){
        int i = Get(x);
        int j = Get(y);
        if(i != j){
            num[i] += num[j];
            par[j] = i;  
        } 
    }
    public bool Same(int x,int y){
        return Get(x) == Get(y);
    }
    int Get(int x){
        if(x != par[x]){
            par[x] = Get(par[x]);
        }
        return par[x];
    }
}

Submission Info

Submission Time
Task C - Interpretation
User leign
Language C# (Mono 4.6.2.0)
Score 400
Code Size 1900 Byte
Status AC
Exec Time 122 ms
Memory 16420 KB

Judge Result

Set Name sample dataset1 dataset2
Score / Max Score 0 / 0 200 / 200 200 / 200
Status
AC × 2
AC × 12
AC × 25
Set Name Test Cases
sample sample-01.txt, sample-02.txt
dataset1 sample-01.txt, sample-02.txt, 01-01.txt, 01-02.txt, 01-03.txt, 01-04.txt, 01-05.txt, 01-06.txt, 01-07.txt, 01-08.txt, 01-09.txt, 01-10.txt
dataset2 sample-01.txt, sample-02.txt, 01-01.txt, 01-02.txt, 01-03.txt, 01-04.txt, 01-05.txt, 01-06.txt, 01-07.txt, 01-08.txt, 01-09.txt, 01-10.txt, 02-01.txt, 02-02.txt, 02-03.txt, 02-04.txt, 02-05.txt, 02-06.txt, 02-07.txt, 02-08.txt, 02-09.txt, 02-10.txt, 02-11.txt, 02-12.txt, 02-13.txt
Case Name Status Exec Time Memory
01-01.txt AC 22 ms 2904 KB
01-02.txt AC 21 ms 2904 KB
01-03.txt AC 22 ms 3032 KB
01-04.txt AC 21 ms 2904 KB
01-05.txt AC 21 ms 2904 KB
01-06.txt AC 21 ms 3016 KB
01-07.txt AC 21 ms 2904 KB
01-08.txt AC 21 ms 3016 KB
01-09.txt AC 21 ms 2904 KB
01-10.txt AC 21 ms 3032 KB
02-01.txt AC 88 ms 14100 KB
02-02.txt AC 96 ms 8760 KB
02-03.txt AC 83 ms 11436 KB
02-04.txt AC 122 ms 14212 KB
02-05.txt AC 101 ms 9496 KB
02-06.txt AC 113 ms 14208 KB
02-07.txt AC 104 ms 9496 KB
02-08.txt AC 90 ms 8632 KB
02-09.txt AC 114 ms 13560 KB
02-10.txt AC 93 ms 15908 KB
02-11.txt AC 93 ms 15908 KB
02-12.txt AC 98 ms 16420 KB
02-13.txt AC 96 ms 16036 KB
sample-01.txt AC 20 ms 2776 KB
sample-02.txt AC 20 ms 2776 KB