Submission #1677090
Source Code Expand
#include <bits/stdc++.h>
using namespace std;
#define int long long
using ll=long long;
using vi=vector<int>;
using pii=pair<int,int>;
#define ALL(c) begin(c),end(c)
#define RALL(c) rbegin(c),rend(c)
#define ITR(i,b,e) for(auto i=(b);i!=(e);++i)
#define FORE(x,c) for(auto &x:c)
#define REPF(i,a,n) for(int i=a,i##len=(int)(n);i<i##len;++i)
#define REP(i,n) REPF(i,0,n)
#define REPR(i,n) for(int i=(int)(n);i>=0;--i)
#define SZ(c) ((int)c.size())
#define CONTAIN(c,x) (c.find(x)!=end(c))
#define OUTOFRANGE(y,x,h,w) (y<0||x<0||y>=h||x>=w)
#define dump(...)
const int DX[9]={0,1,0,-1,1,1,-1,-1,0},DY[9]={-1,0,1,0,-1,1,1,-1,0};
#define INF (1001001001)
#define INFLL (1001001001001001001ll)
template<class T> ostream& operator << (ostream &os,const vector<T> &v) {
ITR(i,begin(v),end(v)) os<<*i<<(i==end(v)-1?"":" "); return os; }
template<class T> istream& operator >> (istream &is,vector<T> &v) {
ITR(i,begin(v),end(v)) is>>*i; return is; }
template<class T> istream& operator >> (istream &is, pair<T,T> &p) {
is>>p.first>>p.second; return is; }
template <class T> bool chmax(T &a,const T &b) {if(a<b) {a=b;return 1;} return 0;}
template <class T> bool chmin(T &a,const T &b) {if(b<a) {a=b;return 1;} return 0;}
template <class T> using heap = priority_queue<T,vector<T>,greater<T>>;
struct before_main_function {
before_main_function() {
#ifdef int
#undef INF
#define INF INFLL
#define stoi stoll
#endif
cin.tie(0);ios::sync_with_stdio(false);
cout<<setprecision(15)<<fixed;
#define endl "\n"
}
} before_main_function;
//------------------8<------------------------------------8<--------------------
pair<vector<int>,int> SCC(vector<vector<int>> &graph) {
int n=SZ(graph);
vector<vector<int>> rg(n);
REP(i,n) FORE(x,graph[i]) rg[x].push_back(i);
priority_queue<pii> pq;
vector<bool> vis(n,false);
int cnt=0;
function<void(int)> dfs1=[&](int v) {
vis[v]=1;
FORE(x,graph[v]) if(!vis[x]) dfs1(x);
pq.push({cnt++,v});
};
REP(i,n) if(!vis[i]) dfs1(i);
cnt=0;
vector<int> group(n,-1);
function<void(int)> dfs2=[&](int v) {
group[v]=cnt;
FORE(x,rg[v]) if(group[x]==-1) dfs2(x);
};
while(!pq.empty()) {
int v=pq.top().second;
pq.pop();
if(group[v]!=-1) continue;
dfs2(v);
cnt++;
}
return {group,cnt};
}
signed main() {
int N,M,K;
cin>>N>>M>>K;
vector<vector<int>> g(N);
vector<char> c(N);
cin>>c;
REP(i,M) {
int a,b;
cin>>a>>b;
a--,b--;
g[a].push_back(b);
}
auto res=SCC(g);
vector<int> scc=res.first;
int sz=res.second;
vector<set<int>> dag(sz);
vector<int> indeg(sz,0);
vector<string> str(sz,"");
vector<bool> vis(N,false);
function<void(int)> dfs=[&](int v) {
vis[v]=1;
str[scc[v]]+=c[v];
FORE(x,g[v]) {
if(scc[v]!=scc[x]) {
if(!CONTAIN(dag[scc[v]],scc[x])) {
dag[scc[v]].insert(scc[x]);
indeg[scc[x]]++;
}
}
if(vis[x]) continue;
dfs(x);
}
};
REP(i,N) {
if(!vis[i]) {
dfs(i);
sort(ALL(str[scc[i]]));
}
}
// topological sort
vector<int> order;
order.reserve(sz);
stack<int> V;
REP(i,sz) if(indeg[i]==0) V.push(i);
while(!V.empty()) {
int v=V.top(); V.pop();
order.push_back(v);
FORE(x,dag[v]) {
indeg[x]--;
if(indeg[x]==0) V.push(x);
}
}
vector<vector<string>> dp(sz,vector<string>(301,"~"));
REP(i,sz) dp[i][0]="";
FORE(v,order) {
REPR(j,300) {
if(dp[v][j]=="~") continue;
REP(l,SZ(str[v])+1) {
assert(j+l<=300);
string tmp=dp[v][j]+str[v].substr(0,l);
chmin(dp[v][j+l],tmp);
}
}
REP(j,301) {
if(dp[v][j]=="~") continue;
FORE(x,dag[v]) {
chmin(dp[x][j],dp[v][j]);
}
}
}
string ans="~";
REP(j,sz) REPF(l,K,301) chmin(ans,dp[j][l].substr(0,K));
if(ans=="~") cout<<-1<<endl;
else cout<<ans<<endl;
return 0;
}
Submission Info
Submission Time |
|
Task |
C - 有向グラフ |
User |
algon |
Language |
C++14 (GCC 5.4.1) |
Score |
0 |
Code Size |
4331 Byte |
Status |
WA |
Exec Time |
26 ms |
Memory |
7168 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 |
2 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 |
2 ms |
256 KB |
subtask1_manual02.txt |
AC |
2 ms |
256 KB |
subtask1_manual03.txt |
AC |
2 ms |
256 KB |
subtask1_manual04.txt |
AC |
2 ms |
256 KB |
subtask1_manual05.txt |
AC |
2 ms |
256 KB |
subtask1_manual06.txt |
AC |
2 ms |
256 KB |
subtask1_manual07.txt |
AC |
2 ms |
256 KB |
subtask1_manual08.txt |
AC |
2 ms |
256 KB |
subtask1_random01.txt |
AC |
4 ms |
896 KB |
subtask1_random02.txt |
AC |
4 ms |
896 KB |
subtask1_random03.txt |
AC |
4 ms |
1152 KB |
subtask1_random04.txt |
AC |
4 ms |
896 KB |
subtask1_random05.txt |
AC |
3 ms |
640 KB |
subtask1_special01.txt |
AC |
2 ms |
384 KB |
subtask1_special02.txt |
AC |
26 ms |
7168 KB |
subtask1_special03.txt |
AC |
24 ms |
7168 KB |
subtask1_special04.txt |
AC |
23 ms |
7168 KB |
subtask1_special05.txt |
AC |
26 ms |
7168 KB |
subtask1_special06.txt |
AC |
13 ms |
2304 KB |
subtask1_special07.txt |
AC |
14 ms |
2304 KB |
subtask1_special08.txt |
AC |
16 ms |
2304 KB |
subtask1_special09.txt |
AC |
13 ms |
2304 KB |
subtask1_special10.txt |
AC |
13 ms |
2304 KB |
subtask1_special11.txt |
WA |
13 ms |
2048 KB |
subtask1_special12.txt |
WA |
14 ms |
1664 KB |
subtask1_special13.txt |
WA |
11 ms |
1408 KB |
subtask1_special14.txt |
AC |
9 ms |
1024 KB |
subtask1_special15.txt |
AC |
17 ms |
1152 KB |