Submission #752282

#	Time	Username	Problem	Language	Result	Execution time	Memory
752282		aykhn	K-th path (IZhO11_kthpath)	C++14	100 / 100	1 ms	340 KiB

kthpath

#include <bits/stdc++.h>

// author: aykhn

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

#define TC int t; cin >> t; while (t--) _();
#define OPT ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define all(v) v.begin(), v.end()
#define mpr make_pair
#define eb emplace_back
#define pb push_back
#define ts to_string
#define fi first
#define se second
#define ins insert
#define int ll
#define inf 0x3F3F3F3F
#define infll 0x3F3F3F3F3F3F3F3FLL
#define bpc __builtin_popcount

int n, m, k;
int ways;
vector<string> v;
vector<pii> rn;
vector<int> a[50];
int used[50][50];
int sum[50];


signed main()
{
    OPT;
    cin >> n >> m;
    v.resize(n + 1, "$");
    vector<vector<int>> dp(n + 1, vector<int> (m + 1, 1));

    for (int i = 1; i <= n; i++)
    {
        string tmp;
        cin >> tmp;

        v[i] += tmp;
    }

    cin >> k;

    for (int i = n - 1; i >= 1; i--)
    {
        for (int j = m - 1; j >= 1; j--)
        {
            dp[i][j] = dp[i + 1][j] + dp[i][j + 1];
        }
    }

    sum[v[1][1] - 'a'] = dp[1][1];

    string ans = "";

    rn.pb(mpr(1, 1));

    used[1][1] = 1;

    while (rn.size())
    {
        int s = 0;
        int ind = 0;
        for (int i = 0; i < 26; i++)
        {
            s += sum[i];
            if (s >= k)
            {
                ind = i;
                break;
            }
        }
        ans.pb(ind + 'a');

        int sz = rn.size();

        vector<pii> nw;

        for (int i = 0; i < sz; i++)
        {
            sum[v[rn[i].fi][rn[i].se] - 'a'] -= dp[rn[i].fi][rn[i].se] * used[rn[i].fi][rn[i].se];
            if (v[rn[i].fi][rn[i].se] - 'a' == ind)
            {
                int x = rn[i].fi;
                int y = rn[i].se;

                if (x + 1 <= n)
                {
                    if (!used[x + 1][y]) nw.pb(mpr(x + 1, y));
                    used[x + 1][y] += used[rn[i].fi][rn[i].se];
                    sum[v[x + 1][y] - 'a'] += dp[x + 1][y] * used[rn[i].fi][rn[i].se];
                }
                if (y + 1 <= m)
                {
                    if (!used[x][y + 1]) nw.pb(mpr(x, y + 1));
                    used[x][y + 1] += used[rn[i].fi][rn[i].se];
                    sum[v[x][y + 1] - 'a'] += dp[x][y + 1] * used[rn[i].fi][rn[i].se];
                }
            }
            else if (v[rn[i].fi][rn[i].se] - 'a' < ind)
            {
                k -= dp[rn[i].fi][rn[i].se] * used[rn[i].fi][rn[i].se];
            }
        }
        rn = nw;
    }

    cout << ans << endl;
}

• Subtask 1: 100 / 100