#include <bits/stdc++.h>
using namespace std;
#define int long long
#define pb push_back
#define pii pair<int,int>
#define all(x) x.begin(), x.end()
#define vi vector<int>
#define inf 2e18
#define spc " ";
template <class T>
void print(T obj) {
std::cout << "{";
for (auto it=obj.begin();it != obj.end();++it){
std::cout << *it;
if (next(it) != obj.end()) std::cout << " ";
}
std::cout << "}\n";
}
void printarr(int* p1,int* p2) {
std::cout << "{";
for (int* ptr = p1;ptr<p2;ptr++) {
std::cout << *ptr;
if (ptr+1 != p2) std::cout << " ";
}
std::cout << "}\n";
}
#define debug(X) std::cout << #X << " = ";print(X);
#define debugarr(A,SZ) std::cout << #A << " = ";printarr(A+1,A+SZ+1);
#define debugint(x) std::cout << #x << " = " << x << endl;
int MOD = 1e9+7;
int mul(int x, int y){return ((x % MOD) * (y % MOD)) % MOD;}
int add(int x, int y){return ((x%MOD)+(y%MOD))%MOD;}
void solve() {
int n,m;
cin >> n >> m;
int grid[n+1][m+1];
for (int i=1;i<=n;i++) {
for (int j=1;j<=m;j++) cin >> grid[i][j];
}
set<int> progs[n+1][m+1];
queue<pair<pair<int,int>,int>> q;
q.push({{1,1},grid[1][1]});
vi dx = {1,0};
vi dy = {0,1};
while (q.size()) {
int x = q.front().first.first;
int y = q.front().first.second;
int d = q.front().second;
q.pop();
for (int i=0;i<2;i++) {
int gx = x+dx[i];
int gy = y+dy[i];
int gd = d+grid[gx][gy];
if (gx > n || gy > m) continue;
if (!progs[gx][gy].count(gd)) {
progs[gx][gy].insert(gd);
q.push({{gx,gy},gd});
}
}
}
cout << ((progs[n][m].count(0))?"YES\n":"NO\n");
}
signed main()
{
#ifdef Local
freopen("in","r",stdin);
freopen("out","w",stdout);
#endif
ios_base::sync_with_stdio(0);cin.tie(0);std::cout.tie(0);
int tc = 1;
cin >> tc;
while (tc--){
//std::cout << "TEST " << cs << ":" << endl;
solve();
}
}
Hello Codeforces, I have submitted the code above to the problem: 1695C - Zero Path My solution got TLE but I am a bit confused with the time complexity. Can you help me?
Your code will do one iteration of bfs for every possible value for every cell. How many possible values can a single cell have? A path from $$$(1, 1)$$$ to $$$(i, j)$$$ goes through $$$i + j - 1$$$ cells. Thus, the smallest possible value you can get on a path to $$$(i, j)$$$ is $$$-i-j+1$$$ (all cells are $$$-1$$$) and the largest one is $$$i+j-1$$$ (all cells are $$$1$$$). Anything in between is also possible (with the same parity). Thus, a cell $$$(i, j)$$$ can have $$$O(i+j)$$$ different values of the path there. Even though all cells cannot simultaneously have the maximum number of different values, I'm confident that there are cases where most cells have a large number of different values. Since each cell can have $$$O(i+j)$$$ different values, the number of bfs iterations will be $$$O(nm(n + m))$$$. Each iteration does mostly $$$O(1)$$$ operations, but
std::set.count()is $$$O(\log(size))$$$ which for cell $$$(i, j)$$$ is $$$O(\log(i + j))$$$ and the time complexity of the code is then $$$O(nm(n+m)\log(n+m))$$$ which is clearly way too slow.Thank you!