Contest Duration: - (local time) (90 minutes) Back to Home

Submission #287933

Source Code Expand

Copy
```#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>
#include<map>
#include<set>
#include<string>
#include<stack>
#include<cstdio>
#include<cmath>
using namespace std;

typedef long long LL;
typedef long double LD;
typedef pair<int,int> P;
typedef pair<int,P> P1;

#define fr first
#define sc second
#define mp make_pair
#define pb push_back
#define rep(i,x) for(int i=0;i<x;i++)
#define rep1(i,x) for(int i=1;i<=x;i++)
#define rrep(i,x) for(int i=x-1;i>=0;i--)
#define rrep1(i,x) for(int i=x;i>0;i--)
#define sor(v) sort(v.begin(),v.end())
#define rev(s) reverse(s.begin(),s.end())
#define lb(vec,a) lower_bound(vec.begin(),vec.end(),a)
#define ub(vec,a) upper_bound(vec.begin(),vec.end(),a)
#define uniq(vec) vec.erase(unique(vec.begin(),vec.end()),vec.end())
#define min_3(a,b,c) min(a,min(b,c))
#define max_3(a,b,c) max(a,max(b,c))
#define mp1(a,b,c) P1(a,P(b,c))
#define pque(a) priority_queue<a>
#define rpque(a) priority_queue<a,vector<a>,greater<a>>

const int INF=1000000000;
const int dre_4[4][2]={{1,0},{0,1},{-1,0},{0,-1}};
const int dre_8[8][2]={{1,0},{1,1},{0,1},{-1,1},{-1,0},{-1,-1},{0,-1},{1,-1}};
const int kaijou[10]={1,1,2,6,24,120,720,5040,40320,362880};

char c[302];

int V;
vector<int> G[302];
vector<int> rG[302];
vector<int> vs;
bool used[302];
int cmp[302];

G[a].pb(b);
rG[b].pb(a);
}

void dfs(int v){
used[v] = true;
rep(i,G[v].size()){
if(!used[G[v][i]])dfs(G[v][i]);
}
vs.pb(v);
}

void rdfs(int v,int k){
used[v] = true;
cmp[v] = k;
rep(i,rG[v].size()){
if(!used[rG[v][i]])rdfs(rG[v][i],k);
}
}

int scc(){
rep(i,302)used[i] = false;
rep(i,V){
if(!used[i])dfs(i);
}
rep(i,302)used[i] = false;
int k = 0;
rrep(i,vs.size()){
if(!used[vs[i]])rdfs(vs[i],k++);
}
return k;
}

vector<int> G_[302];
vector<int> s[302];
vector<string> S[302];

if(cmp[a] != cmp[b])G_[cmp[a]].pb(cmp[b]);
}

void init(){
rep(i,302){
sor(G_[i]);
uniq(G_[i]);
}
rep(i,V){
s[cmp[i]].pb(c[i]);
}
rep(i,302){
sor(s[i]);
}
}

void dfs_(int v){
used[v] = true;
string ans = "";
rep(i,s[v].size())ans += (char)s[v][i];
rep(i,G_[v].size()){
int t = G_[v][i];
dfs_(t);
rep(j,S[t].size()){
S[v].pb(ans + S[t][j]);
}
}
S[v].pb(ans);
}

int main(){
int n,m,k;
int a[1002],b[1002];

scanf("%d%d%d",&n,&m,&k); V = n;
scanf("\n%c",&c[0]);
rep1(i,n-1){
scanf(" %c",&c[i]);
}
rep(i,m){
scanf("%d%d",&a[i],&b[i]); a[i]--; b[i]--;
}
int t = scc();
rep(i,m){
}
init();

/*rep(i,t){
cout << i <<":"<<endl;
rep(j,s[i].size()){
cout << (char)s[i][j] << endl;
}
}*/

rep(i,302)used[i] = false;
string ret = "-1";
rep(i,t){
if(!used[i])dfs_(i);
rep(j,S[i].size()){
string ans = S[i][j];
//cout << ans << endl;
if(ans.size() < k)continue;
string ans_ = "";
int l = 0;
int cnt = ans.size() - k;
rep(r,ans.size()){
while(l > 0 && ans_[l-1] > ans[r] && cnt > 0){
l--;
cnt--;
}
ans_ += 'A';
ans_[l] = ans[r];
l++;
}
ans = "";
rep(i,k){
ans += ans_[i];
}
//cout << "___" << ans <<endl;
if(ret == "-1" || ans < ret)ret = ans;
}
}
if(ret == "{")puts("-1");
else cout << ret << endl;
}
```

#### Submission Info

Submission Time 2014-11-30 12:06:27+0900 C - 有向グラフ yokozuna57 C++11 (GCC 4.8.1) 100 3430 Byte AC 232 ms 7600 KB

#### Compile Error

```./Main.cpp: In function ‘int main()’:
./Main.cpp:124:26: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d%d",&n,&m,&k); V = n;
^
./Main.cpp:125:21: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
scanf("\n%c",&c[0]);
^
./Main.cpp:127:21: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
scanf(" %c",&c[i]);
^
./Main.cpp:130:28: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d",&a[i],&b[i]); a[i]--; b[i]--;
^
```

#### Judge Result

Set Name Sample All
Score / Max Score 0 / 0 100 / 100
Status
 AC × 4
 AC × 32
Set Name Test Cases
Case Name Status Exec Time Memory
subtask0_sample_01.txt AC 21 ms 928 KB
subtask0_sample_02.txt AC 21 ms 924 KB
subtask0_sample_03.txt AC 25 ms 792 KB
subtask0_sample_04.txt AC 22 ms 924 KB
subtask1_manual01.txt AC 22 ms 808 KB
subtask1_manual02.txt AC 22 ms 800 KB
subtask1_manual03.txt AC 22 ms 932 KB
subtask1_manual04.txt AC 23 ms 800 KB
subtask1_manual05.txt AC 21 ms 924 KB
subtask1_manual06.txt AC 22 ms 932 KB
subtask1_manual07.txt AC 23 ms 728 KB
subtask1_manual08.txt AC 21 ms 924 KB
subtask1_random01.txt AC 106 ms 4120 KB
subtask1_random02.txt AC 97 ms 3952 KB
subtask1_random03.txt AC 126 ms 4764 KB
subtask1_random04.txt AC 44 ms 1704 KB
subtask1_random05.txt AC 52 ms 1956 KB
subtask1_special01.txt AC 23 ms 800 KB
subtask1_special02.txt AC 232 ms 7588 KB
subtask1_special03.txt AC 170 ms 7588 KB
subtask1_special04.txt AC 89 ms 7592 KB
subtask1_special05.txt AC 40 ms 7540 KB
subtask1_special06.txt AC 25 ms 1568 KB
subtask1_special07.txt AC 32 ms 1696 KB
subtask1_special08.txt AC 25 ms 1652 KB
subtask1_special09.txt AC 25 ms 1580 KB
subtask1_special10.txt AC 25 ms 1580 KB
subtask1_special11.txt AC 24 ms 1316 KB
subtask1_special12.txt AC 22 ms 1188 KB
subtask1_special13.txt AC 22 ms 1184 KB
subtask1_special14.txt AC 23 ms 864 KB
subtask1_special15.txt AC 43 ms 7600 KB