Submission #1454453
Source Code Expand
#include<iostream>
#include<fstream>
#include<stdio.h>
#include<string>
#include<vector>
#include<map>
#include<math.h>
#include<algorithm>
#include<iomanip>
#include<set>
#define P 1000000007
using namespace std;
int k;
class Node {
public:
int now;
string s;
Node(int n, string str) {
now = n;
s = str;
}
bool operator>(const Node &rhs) const {
return this->s > rhs.s;
}
bool operator<(const Node &rhs) const {
return this->s < rhs.s;
}
};
class G {
public:
vector<vector<int>> p, inv, sp, sinv;
int n, m, l;
vector<string> word;
vector<int> b, c, depth;
vector<bool> a;
G(int nn, vector<vector<int>> &np, vector<vector<int>> &ninv) {
n = nn;
p = np;
inv = ninv;
a.resize(n);
c.resize(n);
for(int i = 0; i < n; i++) {
c[i] = -1;
}
l = 0;
}
void dfs(int i) {
if(a[i]) return;
// cout << i << " " << inv[i].size() << " " << p[i].size() << endl;
a[i] = true;
for(int j = 0; j < p[i].size(); j++) {
if(a[p[i][j]]) {
continue;
}
dfs(p[i][j]);
}
b.push_back(i);
}
void dfs2(int i, int id) {
if(c[i] > -1) return;
c[i] = id;
l++;
for(int j = 0; j < inv[i].size(); j++) {
if(c[inv[i][j]] > -1) continue;
dfs2(inv[i][j], id);
}
}
void solve() {
for(int i = 0; i < n; i++) {
dfs(i);
}
int j = 0;
// for(int i = 0; i < n; i++) cout << b[i] << endl;
for(int i = n - 1; i >= 0; i--) {
if(c[b[i]] > 0) continue;
dfs2(b[i], j++);
}
m = j;
sp.resize(m);
sinv.resize(m);
for(int i = 0; i < n; i++) {
for(int j = 0; j < p[i].size(); j++) {
if(c[i] == c[p[i][j]]) continue;
sp[c[i]].push_back(c[p[i][j]]);
sinv[c[p[i][j]]].push_back(c[i]);
}
}
}
int dfs3(int i) {
if(depth[i] > 0) return depth[i];
int dep = 0;
for(int j = 0; j < sp[i].size(); j++) {
dep = max(dep, dfs3(sp[i][j]));
}
depth[i] = dep + word[i].size();
return depth[i];
}
void solve2(vector<char> d) {
word.resize(m);
for(int i = 0; i < n; i++) {
word[c[i]].push_back(d[i]);
}
for(int i = 0; i < m; i++) {
sort(word[i].begin(), word[i].end());
}
depth.resize(m);
for(int i = 0; i < m; i++) {
dfs3(i);
}
string s = "";
multiset<Node> q;
map<string, bool> f;
for(int i = 0; i < m; i++) {
if(sinv[i].size() == 0) {
for(int j = word[i].size(); j >= 0 && depth[i] - word[i].size() + j >= k; j--) {
if(!f[word[i].substr(0, j) + "a"]) {
q.insert(Node(i, word[i].substr(0, j)));
f[word[i].substr(0, j)] = true;
}
}
}
}
while(q.size() > 0) {
Node now = *q.begin();
q.erase(q.begin());
// cout << now.s << endl;
if(now.s.size() == k) {
cout << now.s << endl;
return;
}
for(int i = 0; i < sp[now.now].size(); i++) {
for(int j = word[sp[now.now][i]].size(); j >= 0 && now.s.size() + depth[sp[now.now][i]] - word[sp[now.now][i]].size() + j >= k; j--) {
if(!f[now.s + word[sp[now.now][i]].substr(0, j) + "a"]) {
q.insert(Node(sp[now.now][i], now.s + word[sp[now.now][i]].substr(0, j)));
f[now.s + word[sp[now.now][i]].substr(0, j)] = true;
}
}
}
}
cout << -1 << endl;
return;
}
};
int main() {
vector<vector<int>> path, inv;
int n, m;
cin >> n >> m >> k;
path.resize(n);
inv.resize(n);
vector<char> c;
c.resize(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--;
path[a].push_back(b);
inv[b].push_back(a);
}
G graph(n, path, inv);
graph.solve();
graph.solve2(c);
return 0;
}
Submission Info
Submission Time |
|
Task |
C - 有向グラフ |
User |
ninja7 |
Language |
C++14 (GCC 5.4.1) |
Score |
100 |
Code Size |
3980 Byte |
Status |
AC |
Exec Time |
18 ms |
Memory |
3072 KB |
Judge Result
Set Name |
Sample |
All |
Score / Max Score |
0 / 0 |
100 / 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 |
AC |
8 ms |
1920 KB |
subtask1_random02.txt |
AC |
9 ms |
1920 KB |
subtask1_random03.txt |
AC |
2 ms |
512 KB |
subtask1_random04.txt |
AC |
5 ms |
1152 KB |
subtask1_random05.txt |
AC |
18 ms |
3072 KB |
subtask1_special01.txt |
AC |
1 ms |
384 KB |
subtask1_special02.txt |
AC |
2 ms |
384 KB |
subtask1_special03.txt |
AC |
2 ms |
384 KB |
subtask1_special04.txt |
AC |
2 ms |
512 KB |
subtask1_special05.txt |
AC |
2 ms |
512 KB |
subtask1_special06.txt |
AC |
2 ms |
384 KB |
subtask1_special07.txt |
AC |
2 ms |
384 KB |
subtask1_special08.txt |
AC |
2 ms |
384 KB |
subtask1_special09.txt |
AC |
2 ms |
384 KB |
subtask1_special10.txt |
AC |
2 ms |
384 KB |
subtask1_special11.txt |
AC |
2 ms |
384 KB |
subtask1_special12.txt |
AC |
2 ms |
384 KB |
subtask1_special13.txt |
AC |
2 ms |
384 KB |
subtask1_special14.txt |
AC |
1 ms |
384 KB |
subtask1_special15.txt |
AC |
2 ms |
512 KB |