Submission #1571222


Source Code Expand

Copy
#include <bits/stdc++.h>
#define FOR(i,bg,ed) for(ll i=(bg);i<(ed);i++)
#define REP(i,n) FOR(i,0,n)
#define REP1(i,n) for(ll i=1;i<=(n);i++)
#define MOD 1000000007
#define int long long
#define all(c) (c).begin(), (c).end()
#define uniq(c) c.erase(unique(all(c)), (c).end())
using namespace std;
typedef long long ll;
const int INF = 1e9;

int N;  //頂点数
int M;  //辺の数
int K;  //回収するアルファベットの数
char C[300];    //頂点に書かれているアルファベット
vector<int> G[300]; //グラフの辺
vector<int> R[300]; //グラフの逆辺
vector<int> G2[300];

bool used[300];
vector<int> vs; //帰りがけ順の並び
int ord[300];   //属する強連結成分のトポロジカル順序
string T[300];

void dfs(int x)
{
    if (used[x]) return;
    used[x] = true;
    for (int t : G[x]) dfs(t);
    vs.push_back(x);
}

void rdfs(int x, int k) {
    if (used[x]) return;
    used[x] = true;
    ord[x] = k;
    for (int t : R[x]) rdfs(t, k);
}

int scc()
{
    REP(i,N) used[i] = false;
    REP(i,N) dfs(i);
    REP(i,N) used[i] = false;
    int k = 0;
    for (int i=vs.size()-1; i>=0; i--) {
        if (!used[vs[i]]) rdfs(vs[i], k++);
    }
    return k;
}

string memo[300][301];
string dp(int x, int k)
{
    if (memo[x][k] != "") return memo[x][k];
    if (k == 0) return "";

    int len = T[x].length();
    string m = "~";
    for (int d=0; d<=min(len,k); d++) {
        string prefix = T[x].substr(0, d);
        string e = "~";
        if (k == d) e = "";
        else {
            for (int t : G2[x]) {
                string o = dp(t, k - d);
                if (o != "~") e = min(e, o);
            }
        }
        if (e != "~") m = min(m, prefix + e);
    }

    return memo[x][k] = m;
}

signed main()
{
    cin >> N >> M >> K;
    REP(i,N) cin >> C[i];
    REP(i,M) {
        int a, b;   //頂点aから頂点bに移動できる辺がある
        cin >> a >> b;
        a--, b--;
        G[a].push_back(b);
        R[b].push_back(a);
    }

    int V = scc();  //強連結成分分解。Vは強連結成分の個数
    REP(i,V) {
        string s = "";
        REP(x,N) if (ord[x] == i) s += C[x];
        sort(s.begin(), s.end());
        T[i] = s;
    }
    REP(x,N) {
        for (int t : G[x]) {
            if (ord[x] != ord[t]) G2[ord[x]].push_back(ord[t]);
        }
    }
    REP(i,V) {
        sort(G2[i].begin(), G2[i].end());
        uniq(G2[i]);
    }

    string s = "~";
    REP(i,V) s = min(s, dp(i, K));
    if (s == "~") s = "-1";
    cout << s << endl;
}

Submission Info

Submission Time
Task C - 有向グラフ
User hiyokko2
Language C++14 (GCC 5.4.1)
Score 100
Code Size 2649 Byte
Status AC
Exec Time 20 ms
Memory 4736 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 2 ms 1024 KB
subtask0_sample_02.txt AC 2 ms 1024 KB
subtask0_sample_03.txt AC 2 ms 1024 KB
subtask0_sample_04.txt AC 2 ms 1024 KB
subtask1_manual01.txt AC 2 ms 1024 KB
subtask1_manual02.txt AC 2 ms 1024 KB
subtask1_manual03.txt AC 2 ms 1024 KB
subtask1_manual04.txt AC 2 ms 1024 KB
subtask1_manual05.txt AC 2 ms 1024 KB
subtask1_manual06.txt AC 2 ms 1024 KB
subtask1_manual07.txt AC 2 ms 1024 KB
subtask1_manual08.txt AC 2 ms 1024 KB
subtask1_random01.txt AC 3 ms 1152 KB
subtask1_random02.txt AC 2 ms 1024 KB
subtask1_random03.txt AC 4 ms 1280 KB
subtask1_random04.txt AC 3 ms 1152 KB
subtask1_random05.txt AC 2 ms 1024 KB
subtask1_special01.txt AC 2 ms 1024 KB
subtask1_special02.txt AC 3 ms 1280 KB
subtask1_special03.txt AC 14 ms 3072 KB
subtask1_special04.txt AC 20 ms 4736 KB
subtask1_special05.txt AC 16 ms 3328 KB
subtask1_special06.txt AC 11 ms 1792 KB
subtask1_special07.txt AC 13 ms 2048 KB
subtask1_special08.txt AC 11 ms 1792 KB
subtask1_special09.txt AC 11 ms 1792 KB
subtask1_special10.txt AC 11 ms 1792 KB
subtask1_special11.txt AC 10 ms 1664 KB
subtask1_special12.txt AC 10 ms 1536 KB
subtask1_special13.txt AC 10 ms 1408 KB
subtask1_special14.txt AC 2 ms 1024 KB
subtask1_special15.txt AC 16 ms 3328 KB