Submission #1636380
Source Code Expand
#include <bits/stdc++.h> using namespace std; using ll = long long; const int MAX_V = 300; int V; vector<int> G[MAX_V]; vector<int> rG[MAX_V]; vector<int> vs; bool used[MAX_V]; int cmp[MAX_V]; void add_edge(int from, int to) { G[from].push_back(to); rG[to].push_back(from); } void dfs(int v) { used[v] = true; for (int i = 0; i < G[v].size(); i++) { if (!used[G[v][i]]) dfs(G[v][i]); } vs.push_back(v); } void rdfs(int v, int k) { used[v] = true; cmp[v] = k; for (int i = 0; i < rG[v].size(); i++) { if (!used[rG[v][i]]) rdfs(rG[v][i], k); } } int scc() { memset(used, 0, sizeof(used)); vs.clear(); for (int v = 0; v < V; v++) { if (!used[v]) dfs(v); } memset(used, 0, sizeof(used)); int k = 0; for (int i = (int)vs.size() - 1; i >= 0; i--) { if (!used[vs[i]]) rdfs(vs[i], k++); } return k; } int n, m, k; char c[305]; string ans[305][305]; string INF(400, 'z'); vector<char> buf; void dfs2(int v) { used[v] = true; buf.push_back(c[v]); for (int i = 0; i < G[v].size(); i++) { if (!used[G[v][i]]) dfs2(G[v][i]); else if (cmp[v] != cmp[G[v][i]]) { for (int j = 1; j <= k; j++) { ans[v][j] = min(ans[v][j], ans[G[v][i]][j]); } } } } int main() { cin.tie(0); ios::sync_with_stdio(false); cin >> n >> m >> k; V = n; for (int i = 0; i < n; i++) { cin >> c[i]; } for (int i = 0; i < m; i++) { int a, b; cin >> a >> b; a--; b--; add_edge(a, b); } scc(); for (int i = 0; i < n; i++) { ans[i][0] = ""; for (int j = 1; j <= k; j++) { ans[i][j] = INF; } } memset(used, 0, sizeof(used)); string res = INF; for (int i = 0; i < vs.size(); i++) { if (used[vs[i]]) continue; buf.clear(); int u = vs[i]; dfs2(u); sort(buf.rbegin(), buf.rend()); for (char ch : buf) { for (int j = k; j >= 0; j--) { if (ans[u][j] == INF) continue; ans[u][min(j + 1, k)] = min(ans[u][min(j + 1, k)], ch + ans[u][j]); } } res = min(res, ans[u][k]); } if (res == INF) cout << -1 << endl; else cout << res << endl; return 0; }
Submission Info
Submission Time | |
---|---|
Task | C - 有向グラフ |
User | fine |
Language | C++14 (GCC 5.4.1) |
Score | 0 |
Code Size | 2474 Byte |
Status | WA |
Exec Time | 12 ms |
Memory | 1536 KB |
Judge Result
Set Name | Sample | All | ||||||
---|---|---|---|---|---|---|---|---|
Score / Max Score | 0 / 0 | 0 / 100 | ||||||
Status |
|
|
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 | WA | 6 ms | 1024 KB |
subtask1_random02.txt | WA | 4 ms | 1024 KB |
subtask1_random03.txt | WA | 8 ms | 1152 KB |
subtask1_random04.txt | WA | 6 ms | 1024 KB |
subtask1_random05.txt | AC | 2 ms | 1024 KB |
subtask1_special01.txt | AC | 8 ms | 1152 KB |
subtask1_special02.txt | AC | 2 ms | 1024 KB |
subtask1_special03.txt | AC | 5 ms | 1152 KB |
subtask1_special04.txt | AC | 8 ms | 1280 KB |
subtask1_special05.txt | AC | 10 ms | 1536 KB |
subtask1_special06.txt | WA | 10 ms | 1152 KB |
subtask1_special07.txt | WA | 6 ms | 1024 KB |
subtask1_special08.txt | WA | 8 ms | 1152 KB |
subtask1_special09.txt | WA | 8 ms | 1152 KB |
subtask1_special10.txt | WA | 8 ms | 1152 KB |
subtask1_special11.txt | WA | 8 ms | 1024 KB |
subtask1_special12.txt | WA | 8 ms | 1152 KB |
subtask1_special13.txt | WA | 10 ms | 1152 KB |
subtask1_special14.txt | AC | 2 ms | 1024 KB |
subtask1_special15.txt | AC | 12 ms | 1024 KB |