Submission #4036083
Source Code Expand
#include<bits/stdc++.h> using namespace std; using ll = int64_t; using P = pair<ll, ll>; ll N, M, K; vector<vector<ll>> edges(300); vector<vector<ll>> ge; vector<string> gstr; const string INF = string(310, 'z'); class StrongDisassembly{ private: ll V; vector<vector<ll>> E; vector<vector<ll>> inv_E; ll *number; bool *used_dfs; ll to_write_num = 0; void dfs(ll now){ used_dfs[now] = 1; for(ll next : E[now]){ if(used_dfs[next]){ continue; } dfs(next); } number[now] = to_write_num++; } void dfs(ll now, bool *used, vector<ll> &ret){ used[now] = 1; ret.push_back(now); for(ll next : inv_E[now]){ if(used[next]){ continue; } dfs(next, used, ret); } } void write_num(){ for(ll i = 0; i < V; i++){ if(!used_dfs[i]){ dfs(i); } } } public: StrongDisassembly(const vector<vector<ll>> &e){ V = e.size(); E = e; inv_E = vector<vector<ll>>(V); number = new ll[V]; used_dfs = new bool[V]; for(ll i = 0; i < V; i++){ used_dfs[i] = 0; inv_E.push_back(vector<ll>(0)); } for(ll i = 0; i < V; i++){ for(ll next : e[i]){ inv_E[next].push_back(i); } } write_num(); } vector<vector<ll>> disassembly(){ vector<vector<ll>> ret; vector<ll> vec; bool used[V] = {}; for(ll i = 0; i < V; i++){ vec.push_back(i); } sort(vec.begin(), vec.end(), [&](ll a, ll b){ return number[a] > number[b]; } ); for(ll vertex : vec){ if(used[vertex]){ continue; } vector<ll> to_insert; dfs(vertex, used, to_insert); ret.push_back(to_insert); } return ret; } }; vector<string> dfs(ll now){ vector<string> memo(K + 1, INF); memo[0] = ""; for(ll nxt : ge[now]){ const auto tmp = move(dfs(nxt)); for(ll j = 0; j <= K; j++) memo[j] = min(memo[j], tmp[j]); } auto update = memo; for(ll i = 1; i <= gstr[now].size(); i++){ for(ll j = 0; i + j <= K; j++){ if(memo[j] != INF){ update[i + j] = min(memo[i + j], gstr[now].substr(0, i) + memo[j]); } } } return update; } int main(){ cin >> N >> M >> K; vector<char> S(N); set<P> se; for(char &c : S) cin >> c; for(ll i = 0; i < M; i++){ ll a, b; cin >> a >> b; edges[--a].push_back(--b); se.insert(P(a, b)); } edges.resize(N); auto g = StrongDisassembly(edges).disassembly(); ge = decltype(ge)(g.size()); gstr = decltype(gstr)(g.size()); vector<ll> rev(N); for(ll i = 0; i < g.size(); i++) for(ll e : g[i]) rev[e] = i; vector<bool> has_parent(ge.size(), false); for(ll i = 0; i < N; i++) for(ll j = 0; j < N; j++) if(se.find(P(i, j)) != se.end() && rev[i] != rev[j]){ ge[rev[i]].push_back(rev[j]); has_parent[rev[j]] = true; } for(auto &v : ge){ sort(v.begin(), v.end()); auto ite = unique(v.begin(), v.end()); v.erase(ite, v.end()); } for(ll i = 0; i < N; i++) gstr[rev[i]] += S[i]; for(auto &s : gstr) sort(s.begin(), s.end()); string ans = INF; for(ll i = 0; i < ge.size(); i++){ if(has_parent[i]) continue; const auto tmp = move(dfs(i)); ans = min(ans, tmp[K]); } if(ans == INF) ans = "-1"; cout << ans << endl; return 0; }
Submission Info
Submission Time | |
---|---|
Task | C - 有向グラフ |
User | kcvlex |
Language | C++14 (GCC 5.4.1) |
Score | 0 |
Code Size | 4213 Byte |
Status | WA |
Exec Time | 14 ms |
Memory | 1152 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 | 1 ms | 256 KB |
subtask0_sample_02.txt | AC | 1 ms | 256 KB |
subtask0_sample_03.txt | AC | 1 ms | 256 KB |
subtask0_sample_04.txt | AC | 1 ms | 256 KB |
subtask1_manual01.txt | AC | 1 ms | 256 KB |
subtask1_manual02.txt | AC | 1 ms | 256 KB |
subtask1_manual03.txt | AC | 1 ms | 256 KB |
subtask1_manual04.txt | AC | 1 ms | 256 KB |
subtask1_manual05.txt | AC | 1 ms | 256 KB |
subtask1_manual06.txt | AC | 1 ms | 256 KB |
subtask1_manual07.txt | AC | 1 ms | 256 KB |
subtask1_manual08.txt | AC | 1 ms | 256 KB |
subtask1_random01.txt | WA | 8 ms | 384 KB |
subtask1_random02.txt | WA | 5 ms | 384 KB |
subtask1_random03.txt | WA | 11 ms | 384 KB |
subtask1_random04.txt | WA | 6 ms | 384 KB |
subtask1_random05.txt | AC | 4 ms | 384 KB |
subtask1_special01.txt | AC | 4 ms | 384 KB |
subtask1_special02.txt | AC | 3 ms | 384 KB |
subtask1_special03.txt | AC | 7 ms | 640 KB |
subtask1_special04.txt | AC | 11 ms | 896 KB |
subtask1_special05.txt | AC | 13 ms | 1152 KB |
subtask1_special06.txt | AC | 12 ms | 512 KB |
subtask1_special07.txt | WA | 9 ms | 512 KB |
subtask1_special08.txt | WA | 12 ms | 512 KB |
subtask1_special09.txt | WA | 12 ms | 512 KB |
subtask1_special10.txt | WA | 12 ms | 512 KB |
subtask1_special11.txt | WA | 11 ms | 512 KB |
subtask1_special12.txt | WA | 11 ms | 512 KB |
subtask1_special13.txt | WA | 11 ms | 384 KB |
subtask1_special14.txt | AC | 2 ms | 256 KB |
subtask1_special15.txt | AC | 14 ms | 1152 KB |