Submission #64098

ソースコード

//#define _GLIBCXX_DEBUG
#include<bits/stdc++.h>
using namespace std;
template <class A, class B> inline bool chmax(A &a, const B &b) { return b > a && (a = b, true); }
template <class A, class B> inline bool chmin(A &a, const B &b) { return b < a && (a = b, true); }
typedef long long ll;
typedef vector<int> vint;
typedef pair<int, int> pint;
typedef vector<long long> vlong;
typedef vector<string> vstring;
#define vpush(a,x) a.push_back(x);
#define rep(i, n) REP(i, 0, n)
#define all(v) v.begin(), v.end()
#define REP(i, x, n) for(int i = x; i < n; i++)
const int INF = 1 << 30;
const int dx[] = {1,0,-1,0,1,1,-1,-1};
const int dy[] = {0,-1,0,1,1,-1,-1,1};
#define stp(x)  setprecision(x)
const long double PI=3.14159265358979323846264338327950;
vector<vector<int> > lis(1005);
vector<int> cnt(1005,0);
vector<vector<int> > fg(1005,vector<int>(1005,-1));
int main(){
  cin.tie(nullptr);
  ios::sync_with_stdio(false);
  int m,n,c;
  cin>>n>>m>>c;
  vint a(m),b(m);
  rep(i,m){
    cin>>a[i]>>b[i];
    lis[a[i]].push_back(b[i]);
    lis[b[i]].push_back(a[i]);
  }
   
  rep(i,n){
   queue<pair<int,int> > que;
   que.emplace(i+1,1);
   fg[i+1][i+1]=0;
   while (!que.empty()){
     int now,p;
     tie(now,p)=que.front(); que.pop();
     if(fg[i+1][now]==-1){
       continue;
     }
     rep(j,lis[now].size()){
       if(fg[i+1][lis[now][j]]==-1){
         fg[i+1][lis[now][j]]=p;
         que.emplace(lis[now][j],p+1);
       }
     }
   }
   rep(j,n){
     if(fg[i+1][j+1]!=-1 && fg[i+1][j+1]<=c && j!=i){
       cnt[i+1]++;
     }
   }
  }
  rep(i,n){
    cout<<cnt[i+1]<<'\n';
  }
  return(0);
}

ステータス

項目	データ
問題	1406 - 友達の友達は友達？
ユーザー名	ei1918
投稿日時	2020-09-16 18:33:17
言語	C++14
状態	Accepted
得点	1
ソースコード長	1667 Byte
最大実行時間	38 ms
最大メモリ使用量	4836 KB

セット

	セット	得点	Cases
1	ALL	1 / 1	*

テストケース

ファイル名	状態	実行時間	メモリ使用量	#
in01.text	AC	25 ms	4572 KB	1
in02.text	AC	21 ms	4616 KB	1
in03.text	AC	19 ms	4656 KB	1
in04.text	AC	22 ms	4688 KB	1
in05.text	AC	25 ms	4600 KB	1
in06.text	AC	19 ms	4512 KB	1
in07.text	AC	25 ms	4540 KB	1
in08.text	AC	21 ms	4560 KB	1
in09.text	AC	25 ms	4456 KB	1
in10.text	AC	27 ms	4476 KB	1
in11.text	AC	20 ms	4616 KB	1
in12.text	AC	28 ms	4512 KB	1
in13.text	AC	24 ms	4652 KB	1
in14.text	AC	29 ms	4656 KB	1
in15.text	AC	38 ms	4656 KB	1
in16.text	AC	20 ms	4656 KB	1
in17.text	AC	26 ms	4672 KB	1
in18.text	AC	23 ms	4688 KB	1
in19.text	AC	22 ms	4732 KB	1
in20.text	AC	21 ms	4760 KB	1
in21.text	AC	32 ms	4644 KB	1
in22.text	AC	28 ms	4644 KB	1
in23.text	AC	19 ms	4780 KB	1
in24.text	AC	33 ms	4820 KB	1
in25.text	AC	30 ms	4712 KB	1
in26.text	AC	26 ms	4616 KB	1
in27.text	AC	20 ms	4524 KB	1
in28.text	AC	20 ms	4672 KB	1
in29.text	AC	19 ms	4812 KB	1
in30.text	AC	29 ms	4836 KB	1
samplein01.text	AC	18 ms	4836 KB	1
samplein02.text	AC	20 ms	4752 KB	1