AtCoder Beginner Contest 030

Submission #961082

Source codeソースコード

#include "bits/stdc++.h"
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
#define rep(i,n) for(ll i=0;i<(ll)(n);i++)
#define all(a)  (a).begin(),(a).end()
#define pb push_back
#define INF (1e9+1)
//#define INF (1LL<<59)



//verified AOJ GRL_3
#define MAX_V 100000
vector<int> G[MAX_V];   //辺
vector<int> rG[MAX_V];  //逆辺
vector<string> str;

void add_edge(int from, int to){
	G[from].push_back(to);
	rG[to].push_back(from);
}

void dfs(int v, bool used[MAX_V], vector<int> &vs){     //末端から遠いノードから順に、たどり着けるノードをvsに入れていく
	used[v] = true;
	rep(i,G[v].size()){
		if(!used[G[v][i]])dfs(G[v][i],used,vs);
	}
	vs.push_back(v);
}

void rdfs(int v,int k,vector<int> &sccs, vector<int> &cmp, bool used[MAX_V]){   //逆辺を使って末端に近いノードから順にDFS
	used[v] = true;
	sccs.push_back(v);
	cmp[v] = k;
	rep(i,rG[v].size()){
		if(!used[rG[v][i]])rdfs(rG[v][i],k,sccs,cmp,used);
	}
}

int scc(int V, vector< vector<int> > &each_scc, vector<int> &cmp){
	vector<int> vs;
	bool used[MAX_V];
	rep(i,MAX_V)used[i] = false;
	vs.clear();
	rep(v,V){
		if(!used[v]) dfs(v, used, vs);
	}
	
	rep(i,MAX_V) used[i] = false;
	int k=0;
	for(int i=vs.size()-1;i>=0;i--){
		vector<int> sccs;
		if(!used[vs[i]]){
			rdfs(vs[i], k++, sccs, cmp, used);
			each_scc.push_back(sccs);
		}
	}
	return k;
}

vector<int> circle_size;

string nom(string s){
	bool f=false;
	string ret="";
	rep(i,s.size()){
		if(s[i]=='0'){
			if(f)ret+=s[i];
		}else{
			f=true;
			ret+=s[i];
		}
	}
	return ret;
}



void sub(string &s){
	for(int i=(int)s.size()-1;i>=0;i--){
		if(s[i]!='0'){
			s[i]--;
			return;
		}
		else{
			s[i]='9';
		}
	}
}

string f(int n){stringstream ss;ss<<n;return ss.str();}


string modstr(int mod,string t){
	int num=0;
	rep(i,t.size()){
		num*=10;
		num+=t[i]-'0';
		num%=mod;
	}
	return f(num);
}

int dfs(int cur, string t,vector<bool> used){
	if( circle_size[cur]!=1 ) t = modstr(circle_size[cur],t);
	
	if(t[0]=='0')t = nom(t);
	if(t=="") return cur;
	
	int to = G[cur][0];
	used[to]=true;
	sub(t);
	return dfs(to,t,used);
}


int main(){
	assert(modstr(123,"379")=="10");
	int v,a;
	string t;
	cin>>v>>a>>t;
	a--;
	vector<int> b(v);
	rep(i,v)cin>>b[i];
	rep(i,v)b[i]--;
	
	rep(i,b.size()) add_edge(i,b[i]);
	vector<vector<int>> each_scc;  //それぞれの強連結成分のリスト
	vector<int> cmp(MAX_V);        //あるノードが属している強連結成分の番号( 多分each_sccに対応している )
	int k = scc(v,each_scc,cmp);   //強連結成分の個数
	
	circle_size.resize(v);
	rep(i,v){
		circle_size[i] = each_scc[cmp[i]].size();
	}
	
	vector<bool> used(v,false);
	used[a]=true;
	cout<<dfs(a,t,used)+1<<endl;
}

Submission

Task問題 D - へんてこ辞書
User nameユーザ名 Yazaten
Created time投稿日時
Language言語 C++11 (GCC 4.9.2)
Status状態 AC
Score得点 100
Source lengthソースコード長 2872 Byte
File nameファイル名
Exec time実行時間 153 ms
Memory usageメモリ使用量 55568 KB

Test case

Set

Set name Score得点 / Max score Cases
Sample - subtask0_sample_01.txt,subtask0_sample_03.txt
Subtask1 50 / 50 subtask0_0.txt,subtask0_1.txt,subtask0_2.txt,subtask0_3.txt,subtask0_4.txt,subtask0_5.txt,subtask0_6.txt,subtask0_7.txt,subtask0_8.txt,subtask0_9.txt,subtask0_sample_01.txt,subtask0_sample_03.txt
All 50 / 50 subtask0_0.txt,subtask0_1.txt,subtask0_2.txt,subtask0_3.txt,subtask0_4.txt,subtask0_5.txt,subtask0_6.txt,subtask0_7.txt,subtask0_8.txt,subtask0_9.txt,subtask0_sample_01.txt,subtask0_sample_03.txt,subtask1_0.txt,subtask1_1.txt,subtask1_10.txt,subtask1_11.txt,subtask1_2.txt,subtask1_3.txt,subtask1_4.txt,subtask1_5.txt,subtask1_6.txt,subtask1_7.txt,subtask1_8.txt,subtask1_9.txt,subtask1_sample_02.txt

Test case

Case name Status状態 Exec time実行時間 Memory usageメモリ使用量
subtask0_0.txt AC 117 ms 22028 KB
subtask0_1.txt AC 86 ms 15896 KB
subtask0_2.txt AC 95 ms 18428 KB
subtask0_3.txt AC 80 ms 14864 KB
subtask0_4.txt AC 102 ms 17868 KB
subtask0_5.txt AC 86 ms 15780 KB
subtask0_6.txt AC 76 ms 15092 KB
subtask0_7.txt AC 92 ms 16752 KB
subtask0_8.txt AC 80 ms 16904 KB
subtask0_9.txt AC 101 ms 17248 KB
subtask0_sample_01.txt AC 31 ms 6168 KB
subtask0_sample_03.txt AC 28 ms 6216 KB
subtask1_0.txt AC 92 ms 21124 KB
subtask1_1.txt AC 153 ms 55568 KB
subtask1_10.txt AC 115 ms 22600 KB
subtask1_11.txt AC 30 ms 6212 KB
subtask1_2.txt AC 104 ms 31372 KB
subtask1_3.txt AC 86 ms 22560 KB
subtask1_4.txt AC 80 ms 15368 KB
subtask1_5.txt AC 138 ms 43232 KB
subtask1_6.txt AC 95 ms 25124 KB
subtask1_7.txt AC 71 ms 12952 KB
subtask1_8.txt AC 118 ms 25928 KB
subtask1_9.txt AC 114 ms 23600 KB
subtask1_sample_02.txt AC 30 ms 6212 KB