Time Complexity

Правка en1, от Number_72, 2023-05-27 10:25:00
#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?

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en1 Английский Number_72 2023-05-27 10:25:00 2367 Initial revision (published)