質問をすることでしか得られない、回答やアドバイスがある。

15分調べてもわからないことは、質問しよう!

新規登録して質問してみよう
ただいま回答率
85.50%
C++

C++はC言語をもとにしてつくられた最もよく使われるマルチパラダイムプログラミング言語の1つです。オブジェクト指向、ジェネリック、命令型など広く対応しており、多目的に使用されています。

Q&A

0回答

201閲覧

AtcoderABC126 E問題に関する質問

sumi_re

総合スコア13

C++

C++はC言語をもとにしてつくられた最もよく使われるマルチパラダイムプログラミング言語の1つです。オブジェクト指向、ジェネリック、命令型など広く対応しており、多目的に使用されています。

0グッド

0クリップ

投稿2019/05/26 15:37

前提・実現したいこと

Atcoder beginner contest 126 E問題に関する質問です。

発生している問題・エラーメッセージ

TLEになってしまい、C++初心者ゆえどこを改善したらいいか分からず、アドバイスいただきたいです。

該当のソースコード

C++

1#include <iostream> 2#include <string> 3#include <vector> 4#include <queue> 5using std::vector; 6using std::find; 7using std::distance; 8using namespace std; 9 10int findIndex(vector<int> v) { 11 //値が-1となるindexを返す 12 int key = -1; 13 int idx; 14 vector<int>::iterator itr = std::find(v.begin(), v.end(), key); 15 idx = std::distance(v.begin(), itr); 16 return idx; 17} 18 19int main() { 20  int N, M; 21  cin >> N >> M; 22   vector<vector<int>> to(N); 23 24 for(int i = 1; i <= M; ++i){ 25 int X ,Y ,Z; 26 cin >> X >> Y >> Z; 27 X--; 28 Y--; 29 to[X].push_back(Y); 30 to[Y].push_back(X); 31 } 32 33 vector<int> ans(N, -1); 34 35 ans[0] = -1; 36 int count = 0; 37 int idx = 0; 38 39 while(true){ 40 queue<int> q; 41 idx = findIndex(ans); 42 if (idx >= N)break; 43 //cout << "idx: " << idx << endl; 44 q.push(idx); 45 46 while(!q.empty()){ 47 int v = q.front(); 48 q.pop(); 49 //cout << "in the first while loop " << "v: " << v << "to[v].size()" << to[v].size() << endl; 50 if(to[v].size() == 0){ 51 //cout << "to[v].size() == 0, idx is " << idx << "and count is " << count << endl; 52 if(ans[idx] != -1) break; 53 ans[idx] = count; 54 break; 55 }else{ 56 for(int i = 0; i < to[v].size(); ++i){ 57 //cout << "size" << i << ":" << to[v].size() << endl; 58 int u = to[v][i]; 59 if(ans[u] != -1) break; 60 ans[u] = count; 61 //cout << "to[v].size() != 0, u is " << u << "and count is " << count << endl; 62 q.push(u); 63 }//end of for loop 64 }//end of else 65 }// 66 count++; 67 //cout << "count increment" << endl; 68 } 69 cout << count << endl; 70 return 0; 71}

試したこと

一つのノードから辿れるノードに同じ番号をつけ、異なる番号のものをカウントし、提出しています。

補足情報(FW/ツールのバージョンなど)

ここにより詳細な情報を記載してください。

気になる質問をクリップする

クリップした質問は、後からいつでもMYページで確認できます。

またクリップした質問に回答があった際、通知やメールを受け取ることができます。

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

1T2R3M4

2019/05/26 23:55

プロファイリング結果はどうなっていますか。
guest

あなたの回答

tips

太字

斜体

打ち消し線

見出し

引用テキストの挿入

コードの挿入

リンクの挿入

リストの挿入

番号リストの挿入

表の挿入

水平線の挿入

プレビュー

まだ回答がついていません

会員登録して回答してみよう

アカウントをお持ちの方は

15分調べてもわからないことは
teratailで質問しよう!

ただいまの回答率
85.50%

質問をまとめることで
思考を整理して素早く解決

テンプレート機能で
簡単に質問をまとめる

質問する

関連した質問