Submission #3548341


Source Code Expand

#include <bits/stdc++.h>
#include <unordered_set>
using namespace std;
#define ll long long
#define rep(i,n) for(int (i)=0;(i)<(n);(i)++)
#define repeat(i,s,n) for(int (i)=s; (i)<(n); (i)++)
#define revrep(i,n) for(int (i)=(n)-1;i>=0; i--)
const ll p = 1e9+7;
int main() {
  cin.tie(0);
  ios::sync_with_stdio(false);
  cout<<setprecision(std::numeric_limits<float>::max_digits10);
  map<int,vector<int>> es;
  int n,a,b,m;
  cin>>n>>a>>b>>m;
  rep(i,m) {
    int x,y;
    cin>>x>>y;
    es[x].push_back(y);
    es[y].push_back(x);
  }
  vector<bool> visited(n+1);
  queue<int> q;
  q.push(a);
  vector<int> dist(n+1);
  vector<ll> comb(n+1);
  comb[a]=1;
  dist[a]=0;
  visited[a]=true;
  while(!q.empty()) {
    int v = q.front();
    q.pop();
    for(auto& u : es[v]) {
      if(!visited[u]) {
        dist[u]=dist[v]+1;
        visited[u]=true;
        q.push(u);
      }
      if(dist[u]==dist[v]+1) {
        comb[u]+=comb[v];
        comb[u]%=p;
      }
    }
  }
  cout << comb[b]<<endl;
  return 0;
}
// noteton
// https://beta.atcoder.jp/contests/abc021/submissions/1172933 このひとsubtask21wa

Submission Info

Submission Time
Task C - 正直者の高橋くん
User ponpon05
Language C++14 (GCC 5.4.1)
Score 100
Code Size 1157 Byte
Status AC
Exec Time 1 ms
Memory 256 KB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 100 / 100
Status
AC × 2
AC × 32
Set Name Test Cases
Sample subtask0_sample_01.txt, subtask0_sample_02.txt
All subtask0_sample_01.txt, subtask0_sample_02.txt, subtask1_01.txt, subtask1_02.txt, subtask1_03.txt, subtask1_04.txt, subtask1_05.txt, subtask1_06.txt, subtask1_07.txt, subtask1_08.txt, subtask1_09.txt, subtask1_10.txt, subtask1_11.txt, subtask1_12.txt, subtask1_13.txt, subtask1_14.txt, subtask1_15.txt, subtask1_16.txt, subtask1_17.txt, subtask1_18.txt, subtask1_19.txt, subtask1_20.txt, subtask1_21.txt, subtask1_22.txt, subtask1_23.txt, subtask1_24.txt, subtask1_25.txt, subtask1_26.txt, subtask1_27.txt, subtask1_28.txt, subtask1_29.txt, subtask1_30.txt
Case Name Status Exec Time Memory
subtask0_sample_01.txt AC 1 ms 256 KB
subtask0_sample_02.txt AC 1 ms 256 KB
subtask1_01.txt AC 1 ms 256 KB
subtask1_02.txt AC 1 ms 256 KB
subtask1_03.txt AC 1 ms 256 KB
subtask1_04.txt AC 1 ms 256 KB
subtask1_05.txt AC 1 ms 256 KB
subtask1_06.txt AC 1 ms 256 KB
subtask1_07.txt AC 1 ms 256 KB
subtask1_08.txt AC 1 ms 256 KB
subtask1_09.txt AC 1 ms 256 KB
subtask1_10.txt AC 1 ms 256 KB
subtask1_11.txt AC 1 ms 256 KB
subtask1_12.txt AC 1 ms 256 KB
subtask1_13.txt AC 1 ms 256 KB
subtask1_14.txt AC 1 ms 256 KB
subtask1_15.txt AC 1 ms 256 KB
subtask1_16.txt AC 1 ms 256 KB
subtask1_17.txt AC 1 ms 256 KB
subtask1_18.txt AC 1 ms 256 KB
subtask1_19.txt AC 1 ms 256 KB
subtask1_20.txt AC 1 ms 256 KB
subtask1_21.txt AC 1 ms 256 KB
subtask1_22.txt AC 1 ms 256 KB
subtask1_23.txt AC 1 ms 256 KB
subtask1_24.txt AC 1 ms 256 KB
subtask1_25.txt AC 1 ms 256 KB
subtask1_26.txt AC 1 ms 256 KB
subtask1_27.txt AC 1 ms 256 KB
subtask1_28.txt AC 1 ms 256 KB
subtask1_29.txt AC 1 ms 256 KB
subtask1_30.txt AC 1 ms 256 KB