Submission #287667


Source Code Expand

using System;
using System.Collections;
using System.Collections.Generic;
using System.Linq;
using System.IO;

class Myon
{
    public Myon() { }
    public static int Main()
    {
        new Myon().calc();
        return 0;
    }

    int n, m, k;
    char[] c;
    bool[,] con;
    bool[,] con2;

    List<int>[] es;
    List<int>[] esrev;

    List<char>[] cs;
    string[] st;

    void calc()
    {
        Scanner cin = new Scanner();
        n = cin.nextInt();
        m = cin.nextInt();
        k = cin.nextInt();
        c = new char[n];
        for (int i = 0; i < n; i++)
        {
            c[i] = cin.next()[0];
        }
        con = new bool[n, n];
        int[] a, b;
        a = new int[m];
        b = new int[m];
        for (int i = 0; i < m; i++)
        {
            a[i] = cin.nextInt() - 1;
            b[i] = cin.nextInt() - 1;
            con[a[i], b[i]] = true;
        }

        con2 = (bool[,])con.Clone();

        for (int k2 = 0; k2 < n; k2++)
        {
            for (int i = 0; i < n; i++)
            {
                for (int j = 0; j < n; j++)
                {
                    con2[i, j] |= con2[i, k2] & con2[k2, j];
                }
            }
        }
        uni = new int[n];
        for (int i = 0; i < n; i++)
        {
            uni[i] = -1;
        }

        for (int i = 0; i < n; i++)
        {
            for (int j = i + 1; j < n; j++)
            {
                if (con2[i, j] && con2[j, i])
                {
                    connect(i, j);
                }
            }
        }

        es = new List<int>[n];
        esrev = new List<int>[n];
        for (int i = 0; i < n; i++)
        {
            es[i] = new List<int>();
            esrev[i] = new List<int>();
        }

        int[] count = new int[n];

        for (int i = 0; i < m; i++)
        {
            int groupa = getuni(a[i]);
            int groupb = getuni(b[i]);
            if (groupa == groupb) continue;
            if (!es[groupa].Contains(groupb))
            {
                es[groupa].Add(groupb);
                esrev[groupb].Add(groupa);
                count[groupb]++;
            }
        }

        cs = new List<char>[n];
        for (int i = 0; i < n; i++)
        {
            cs[i] = new List<char>();
        }

        for (int i = 0; i < n; i++)
        {
            cs[getuni(i)].Add(c[i]);
        }

        for (int i = 0; i < n; i++)
        {
            cs[i].Sort();
        }

        st = new string[n];
        for (int i = 0; i < n; i++)
        {
            st[i] = new string(cs[i].ToArray());
        }

        string ng = (char)('z' + 1) + "";

        Queue<int> q = new Queue<int>();

        for (int i = 0; i < n; i++)
        {
            if (cs[i].Count == 0) continue;
            if (count[i] == 0) q.Enqueue(i);
        }

        string[,] dp = new string[n, k + 1];
        for (int i = 0; i < n; i++)
        {
            for (int j = 0; j < k + 1; j++)
            {
                dp[i, j] = ng;
            }
            dp[i, 0] = "";
        }

        string ret = ng;
        while (q.Count != 0)
        {
            int now = q.Dequeue();
            for (int i = k; i >= 0; i--)
            {
                if (dp[now, i] == ng) continue;
                for (int j = 1; i + j < k + 1 && j <= st[now].Length; j++)
                {
                    string nextstring = dp[now, i] + st[now].Substring(0, j);
                    if (String.CompareOrdinal(nextstring, dp[now, i + j]) < 0)
                    {
                        dp[now, i + j] = nextstring;
                    }
                }
            }
            foreach (var next in es[now])
            {
                for (int i = 0; i < k + 1; i++)
                {
                    if (String.CompareOrdinal(dp[now, i], dp[next, i]) < 0)
                    {
                        dp[next, i] = dp[now, i];
                    }
                }

                count[next]--;
                if (count[next] == 0) q.Enqueue(next);
            }

            if (String.CompareOrdinal(dp[now, k], ret) < 0)
            {
                ret = dp[now, k];
            }

        }

        if (ret == ng) Console.WriteLine(-1);
        else Console.WriteLine(ret);
    }

    int[] uni;

    int getuni(int a)
    {
        if (uni[a] < 0) return a;
        else return uni[a] = getuni(uni[a]);
    }

    bool connect(int a, int b)
    {
        a = getuni(a);
        b = getuni(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;
    }

    //swap
    void swap<T>(ref T a, ref T b)
    {
        T c = a;
        a = b;
        b = c;
    } 
    


}




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++];
        do
        {
            s = Console.ReadLine().Split(cs, StringSplitOptions.RemoveEmptyEntries);
        } while ((s.Length == 1 && s[0] == "") || s.Length == 0);
        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 C - 有向グラフ
User chokudai
Language C# (Mono 2.10.8.1)
Score 100
Code Size 5743 Byte
Status AC
Exec Time 688 ms
Memory 21056 KB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 100 / 100
Status
AC × 4
AC × 32
Set Name Test Cases
Sample subtask0_sample_01.txt, subtask0_sample_02.txt, subtask0_sample_03.txt, subtask0_sample_04.txt
All subtask0_sample_01.txt, subtask0_sample_02.txt, subtask0_sample_03.txt, subtask0_sample_04.txt, subtask1_manual01.txt, subtask1_manual02.txt, subtask1_manual03.txt, subtask1_manual04.txt, subtask1_manual05.txt, subtask1_manual06.txt, subtask1_manual07.txt, subtask1_manual08.txt, subtask1_random01.txt, subtask1_random02.txt, subtask1_random03.txt, subtask1_random04.txt, subtask1_random05.txt, subtask1_special01.txt, subtask1_special02.txt, subtask1_special03.txt, subtask1_special04.txt, subtask1_special05.txt, subtask1_special06.txt, subtask1_special07.txt, subtask1_special08.txt, subtask1_special09.txt, subtask1_special10.txt, subtask1_special11.txt, subtask1_special12.txt, subtask1_special13.txt, subtask1_special14.txt, subtask1_special15.txt
Case Name Status Exec Time Memory
subtask0_sample_01.txt AC 178 ms 9228 KB
subtask0_sample_02.txt AC 176 ms 9292 KB
subtask0_sample_03.txt AC 170 ms 9308 KB
subtask0_sample_04.txt AC 161 ms 9212 KB
subtask1_manual01.txt AC 171 ms 9284 KB
subtask1_manual02.txt AC 169 ms 9288 KB
subtask1_manual03.txt AC 171 ms 9288 KB
subtask1_manual04.txt AC 173 ms 9280 KB
subtask1_manual05.txt AC 169 ms 9280 KB
subtask1_manual06.txt AC 172 ms 9244 KB
subtask1_manual07.txt AC 168 ms 9288 KB
subtask1_manual08.txt AC 178 ms 9516 KB
subtask1_random01.txt AC 655 ms 10476 KB
subtask1_random02.txt AC 647 ms 9808 KB
subtask1_random03.txt AC 656 ms 11756 KB
subtask1_random04.txt AC 648 ms 10444 KB
subtask1_random05.txt AC 652 ms 9548 KB
subtask1_special01.txt AC 647 ms 9940 KB
subtask1_special02.txt AC 662 ms 9748 KB
subtask1_special03.txt AC 653 ms 12884 KB
subtask1_special04.txt AC 672 ms 18124 KB
subtask1_special05.txt AC 685 ms 21056 KB
subtask1_special06.txt AC 680 ms 15144 KB
subtask1_special07.txt AC 677 ms 12492 KB
subtask1_special08.txt AC 682 ms 15168 KB
subtask1_special09.txt AC 684 ms 15056 KB
subtask1_special10.txt AC 678 ms 15108 KB
subtask1_special11.txt AC 680 ms 14288 KB
subtask1_special12.txt AC 677 ms 13760 KB
subtask1_special13.txt AC 679 ms 13564 KB
subtask1_special14.txt AC 628 ms 9176 KB
subtask1_special15.txt AC 688 ms 11512 KB