Submission #1736584
Source Code Expand
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<int> vint;
typedef pair<int,int> pint;
typedef vector<pint> vpint;
#define rep(i,n) for(int i=0;i<(n);i++)
#define REP(i,n) for(int i=n-1;i>=(0);i--)
#define reps(i,f,n) for(int i=(f);i<(n);i++)
#define each(it,v) for(__typeof((v).begin()) it=(v).begin();it!=(v).end();it++)
#define all(v) (v).begin(),(v).end()
#define eall(v) unique(all(v), v.end())
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define chmax(a, b) a = (((a)<(b)) ? (b) : (a))
#define chmin(a, b) a = (((a)>(b)) ? (b) : (a))
const int MOD = 1e9 + 7;
const int INF = 1e9;
const ll INFF = 1e18;
int n, m, k;
char c[310];
int a[1010], b[1010];
class strongly_connected_components{
public:
vector<vector<int> > G, rG;
vector<int> used, vs;
vector<int> cmp; //cmp[v] := 頂点vが含まれる連結成分がどれなのかを示す番号
strongly_connected_components(int n): G(n), rG(n), cmp(n), used(n){}
void add_edge(int from, int to){
G[from].push_back(to);
rG[to].push_back(from);
}
int scc(){
fill(used.begin(), used.end(), 0);
vs.clear();
for (int i = 0; i < G.size(); ++i){
if(!used[i]) dfs(i);
}
fill(used.begin(), used.end(), 0);
int k = 0;
for (int i = vs.size() - 1; i >= 0; --i){
if(!used[vs[i]]){
rdfs(vs[i], k++);
}
}
return k; //sccの数
}
private:
void dfs(int curr){
used[curr] = true;
for(auto next : G[curr]){
if(!used[next]) dfs(next);
}
vs.push_back(curr);
}
void rdfs(int curr, int k){
used[curr] = true;
cmp[curr] = k;//頂点vに対して、k番目と強連結成分であること入れる
for(auto next : rG[curr]){
if(!used[next]) rdfs(next, k);
}
}
};
vector<int> G[310];
string memo[310];
//dp[i][j] := i番目の連結成分までを見て, 文字列の長さがjとなるときの最小文字列
string dp[310][310];
void dfs(int u, int pre) {
for(auto v : G[u]) {
if(u == pre) continue;
rep(j, k + 1)rep(len, memo[v].size() + 1) {
string tm = dp[u][j] + memo[v].substr(0, len);
if(tm.size() > k) continue;
if(dp[v][j + len] > tm) dp[v][j + len] = tm;
}
dfs(v, u);
}
}
int main(void) {
cin >> n >> m >> k;
rep(i, n) cin >> c[i];
rep(i, m) cin >> a[i] >> b[i];
rep(i, m) a[i]--, b[i]--;
strongly_connected_components scc(n);
rep(i, m) scc.add_edge(a[i], b[i]);
vector<int> tG[310];
rep(i, m) tG[a[i]].pb(b[i]);
int size = scc.scc();
// printf("size %d\n", size);
set<int> st[310];
rep(u, n) {
for(auto v : tG[u]) if(scc.cmp[u] != scc.cmp[v]) st[scc.cmp[u]].insert(scc.cmp[v]);
}
rep(u, 310) for(auto v : st[u]) {
G[u].pb(v);
// printf("u %d -> v %d\n", u, v);
}
rep(i, 310) { // i番目の連結成分
vector<char> t;
rep(j, n){ // 頂点番号
if(scc.cmp[j] == i) t.pb(c[j]);
}
sort(all(t));
string s;
for(auto u : t) s += u;
memo[i] = s;
}
// rep(i, size) cout << i << " " << memo[i] << endl;
rep(i, 310)rep(j, 310) dp[i][j] ="{";
rep(i, size) rep(j, memo[i].size() + 1) {
if(j <= k) dp[i][j] = memo[i].substr(0, j);
}
dfs(0, -1);
string ans = "{";
rep(i, size) if(ans > dp[i][k]) ans = dp[i][k];
if(ans == "{") printf("-1\n");
else cout << ans << endl;
return 0;
}
Submission Info
Submission Time |
|
Task |
C - 有向グラフ |
User |
mmxsrup |
Language |
C++14 (GCC 5.4.1) |
Score |
0 |
Code Size |
3364 Byte |
Status |
WA |
Exec Time |
31 ms |
Memory |
9856 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 |
9 ms |
5504 KB |
subtask0_sample_02.txt |
AC |
9 ms |
5504 KB |
subtask0_sample_03.txt |
AC |
9 ms |
5504 KB |
subtask0_sample_04.txt |
AC |
9 ms |
5504 KB |
subtask1_manual01.txt |
AC |
9 ms |
5504 KB |
subtask1_manual02.txt |
AC |
9 ms |
5504 KB |
subtask1_manual03.txt |
AC |
9 ms |
5504 KB |
subtask1_manual04.txt |
AC |
9 ms |
5504 KB |
subtask1_manual05.txt |
AC |
9 ms |
5504 KB |
subtask1_manual06.txt |
AC |
9 ms |
5504 KB |
subtask1_manual07.txt |
AC |
9 ms |
5504 KB |
subtask1_manual08.txt |
AC |
9 ms |
5504 KB |
subtask1_random01.txt |
WA |
17 ms |
5760 KB |
subtask1_random02.txt |
WA |
12 ms |
5632 KB |
subtask1_random03.txt |
WA |
10 ms |
5632 KB |
subtask1_random04.txt |
AC |
17 ms |
5760 KB |
subtask1_random05.txt |
AC |
10 ms |
5632 KB |
subtask1_special01.txt |
AC |
10 ms |
5632 KB |
subtask1_special02.txt |
AC |
11 ms |
5632 KB |
subtask1_special03.txt |
AC |
17 ms |
6656 KB |
subtask1_special04.txt |
AC |
25 ms |
8704 KB |
subtask1_special05.txt |
AC |
31 ms |
9728 KB |
subtask1_special06.txt |
AC |
26 ms |
7040 KB |
subtask1_special07.txt |
AC |
18 ms |
6272 KB |
subtask1_special08.txt |
AC |
26 ms |
7040 KB |
subtask1_special09.txt |
AC |
26 ms |
7040 KB |
subtask1_special10.txt |
AC |
26 ms |
7040 KB |
subtask1_special11.txt |
AC |
25 ms |
6656 KB |
subtask1_special12.txt |
AC |
25 ms |
6400 KB |
subtask1_special13.txt |
AC |
23 ms |
6272 KB |
subtask1_special14.txt |
AC |
10 ms |
5632 KB |
subtask1_special15.txt |
AC |
31 ms |
9856 KB |