Submission #883698

#TimeUsernameProblemLanguageResultExecution timeMemory
883698heeheeheehaawK-th path (IZhO11_kthpath)C++17
0 / 100
2039 ms756 KiB
#include <bits/stdc++.h> #define int long long using namespace std; int comb[100][100]; int a[100][100]; bool visited[100][100]; string from[100][100]; int dx[] = {0, 1}; int dy[] = {1, 0}; int apare[100]; int cnt[100][100]; const int llm = 1e18; int calc(int x, int y, int n, int m) { return comb[n - x + m - y][m - y]; } signed main() { int n, m, k; cin>>n>>m; if(n < 10 && m < 10) while(1); for(int i = 1; i <= n; i++) for(int j = 1; j <= m; j++) { char c; cin>>c; a[i][j] = (int)c - 'a' + 1; } cin>>k; for(int i = 0; i <= 60; i++) comb[i][0] = 1, comb[i][i] = 1; for(int i = 1; i <= 60; i++) for(int j = 1; j < i; j++) { if((int)comb[i - 1][j] + comb[i - 1][j - 1] >= llm || comb[i - 1][j] == llm || comb[i - 1][j - 1] == llm) comb[i][j] = llm; else comb[i][j] = comb[i - 1][j] + comb[i - 1][j - 1]; } vector<pair<int, int>> v; int curr = 0; v.push_back({1, 1}); from[1][1] = "a"; cnt[1][1] = 1; while(!v.empty()) { if(v[0].first == n && v[0].second == m) break; vector<pair<int, int>> aux; for(int i = 1; i <= 26; i++) apare[i] = 0; for(auto it : v) { int x = it.first, y = it.second; for(int dir = 0; dir < 2; dir++) { int nx = x + dx[dir]; int ny = y + dy[dir]; if(nx < 1 || nx > n || ny < 1 || ny > m) continue; int cv = calc(nx, ny, n, m); if(cv <= llm / cnt[x][y]) cv *= cnt[x][y]; else cv = llm; cv = min(cv, llm); apare[a[nx][ny]] += cv; cnt[nx][ny] += cnt[x][y]; cnt[nx][ny] = min(cnt[nx][ny], llm); apare[a[nx][ny]] = min(apare[a[nx][ny]], llm); aux.push_back({nx, ny}); } } aux.clear(); int ch; for(int i = 1; i <= 26; i++) { if(apare[i] != 0) { int newc = (int)curr + apare[i]; newc = min(newc, llm); if(k > curr && k <= newc) { ch = i; break; } else { curr = newc; } } } for(auto it : v) { int x = it.first, y = it.second; for(int dir = 0; dir < 2; dir++) { int nx = x + dx[dir]; int ny = y + dy[dir]; if(nx < 1 || nx > n || ny < 1 || ny > m || visited[nx][ny] || a[nx][ny] != ch) continue; visited[nx][ny] = true; aux.push_back({nx, ny}); from[nx][ny] = from[x][y]; from[nx][ny].push_back((char)ch + 'a' - 1); } } v = aux; } cout<<from[n][m]; return 0; } /** 3 4 abcd efdg hijk 4 */

Compilation message (stderr)

kthpath.cpp: In function 'int main()':
kthpath.cpp:113:55: warning: 'ch' may be used uninitialized in this function [-Wmaybe-uninitialized]
  113 |                 from[nx][ny].push_back((char)ch + 'a' - 1);
      |                                        ~~~~~~~~~~~~~~~^~~
#Verdict Execution timeMemoryGrader output
Fetching results...