fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define int long long
  4. #define dd double
  5. #define ld long double
  6. #define ull unsigned long long
  7. #define yes cout << "YES\n"
  8. #define no cout << "NO\n"
  9. #define el "\n"
  10. #define Arwa ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  11. #define fix(x) cout << fixed << setprecision(x)
  12. #define all(v) v.begin(),v.end()
  13. #define dpp(v,val) memset(v,val,sizeof(v))
  14. #define mod 1e9+7
  15. #define oo 1e9
  16. const int N = 1e5 + 5;
  17. int n,m;
  18. vector<vector<int>>v;
  19. map<pair<int,int>,bool>mp;
  20. int dp[1003][1003];
  21. bool valid(int i,int j)
  22. {
  23.     if(mp[{i,j}]==1) return false;
  24.     return (i>=1&&i<=n&&j>=1&&j<=m);
  25. }
  26. int solve(int i,int j)
  27. {
  28.   if(!valid(i,j)) return 0;
  29.   int& ret =dp[i][j];
  30.   if(ret!=-1) return ret;
  31.   if(i==n&&j==m) return 1;
  32.   ret=solve(i,j+1)+solve(i+1,j);
  33.   return ret;
  34. }
  35. void HereWeGoAgain()
  36. {
  37.     mp.clear();
  38.     cin>>n>>m;
  39.     cin.ignore();
  40.     v.resize(n);
  41.     for(int i=0;i<n;i++)
  42.     {
  43.         int x;
  44.         string s;
  45.         getline(cin,s);
  46.         vector<int>v;
  47.         stringstream ss(s);
  48.         while(ss>>x)
  49.         v.push_back(x);
  50.         for(int j=1;j<v.size();j++) mp[{v[0],v[j]}]=1;
  51.     }
  52.     dpp(dp,-1);
  53.     //for(auto it:mp) if(it.second) cout<<it.first.first<<' '<<it.first.second<<el;
  54.     cout<<solve(1,1);
  55. }
  56. int32_t main() 
  57. {
  58.     Arwa
  59.     int t=1;
  60.     cin>>t;
  61.     for(int i=1;i<=t;i++)
  62.     {
  63.     HereWeGoAgain();
  64.     if(i!=t) cout<<el<<el;
  65.     }
  66.     return 0;
  67. }
Success #stdin #stdout 0.01s 11388KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/osljmA
language:
C++ (gcc 8.3)
created:
1 day ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!