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];

void add_edge(int a,int b){
	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];

void add_edge_(int a,int b){
	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]--;
		add_edge(a[i],b[i]);
	}
	int t = scc();
	rep(i,m){
		add_edge_(a[i],b[i]);
	}
	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
Task C - 有向グラフ
User yokozuna57
Language C++11 (GCC 4.8.1)
Score 100
Code Size 3430 Byte
Status AC
Exec Time 232 ms
Memory 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
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 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