Submission #683304

#TimeUsernameProblemLanguageResultExecution timeMemory
683304vovamrK-th path (IZhO11_kthpath)C++17
100 / 100
7 ms572 KiB
#include <bits/stdc++.h> #include <ext/pb_ds/assoc_container.hpp> #include <ext/pb_ds/tree_policy.hpp> #define fi first #define se second #define ll long long #define ld long double #define sz(x) ((int)(x).size()) #define all(x) (x).begin(), (x).end() #define pb push_back #define mpp make_pair #define ve vector using namespace std; using namespace __gnu_pbds; template<class T> using oset = tree<T,null_type,less<T>,rb_tree_tag,tree_order_statistics_node_update>; const ll inf = 1e18; const int iinf = 1e9; typedef pair<ll, ll> pll; typedef pair<int, int> pii; mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count()); template <typename T> inline bool chmin(T& a, T b) { return (a > b ? a = b, 1 : 0); } template <typename T> inline bool chmax(T& a, T b) { return (a < b ? a = b, 1 : 0); } inline void solve() { /* #ifndef LOCAL const string NAME = "kthpath"; ifstream cin(NAME + ".in"); ofstream cout(NAME + ".out"); #endif */ int n, m; cin >> n >> m; ve<ve<char>> a(n, ve<char>(m)); for (auto &i : a) for (auto &j : i) cin >> j; ve<ve<ll>> dp(n, ve<ll> (m)); dp[n - 1][m - 1] = 1; for (int i = n - 1; ~i; --i) { for (int j = m - 1; ~j; --j) { if (i + 1 < n) dp[i][j] += dp[i + 1][j]; if (j + 1 < m) dp[i][j] += dp[i][j + 1]; } } ll k; cin >> k; string result(1, a[0][0]); map<string,ve<array<ll,3>>> cand; cand[string(1, a[0][0])] = {{1, 0, 0}}; while (sz(result) < n + m - 1) { map<string,ve<array<ll,3>>> cur; // cout << "have " << result << " " << sz(result) << " " << k << '\n'; string S = cand.begin()->fi; for (auto &[ways, x, y] : cand.begin()->se) { // cout << x << " " << y << " " << ways << endl; if (x + 1 < n) { cur[S + a[x + 1][y]].pb({ways, x + 1, y}); } if (y + 1 < m) { cur[S + a[x][y + 1]].pb({ways, x, y + 1}); } } // cout << "built new strings" << endl; for (auto &[str, V] : cur) { auto vec = V; ve<array<ll,3>> c; // cout << str << endl; sort(all(vec)); for (int i = 0; i < sz(vec); ++i) { if (!sz(c) || mpp(c.back()[1], c.back()[2]) != mpp(vec[i][1], vec[i][2])) c.pb(vec[i]); else c.back()[0] += vec[i][0]; } V = c; } // cout << "erased duplicates -> " << sz(cur) << endl; map<string,ve<array<ll,3>>> nw; for (auto &[str, vec] : cur) { ll tot = 0; for (auto &[ways, x, y] : vec) tot += ways * dp[x][y]; if (k > tot) { k -= tot; } else { nw[str] = vec; break; } } // cout << "found new" << endl << endl; // assert(sz(nw) == 1); swap(cand, nw); result = cand.begin()->fi; } cout << result; } signed main() { ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0); int q = 1; // cin >> q; while (q--) solve(); cerr << fixed << setprecision(3) << "Time execution: " << (double)clock() / CLOCKS_PER_SEC << endl; }
#Verdict Execution timeMemoryGrader output
Fetching results...