Submission #1325872

#	Time	Username	Problem	Language	Result	Execution time	Memory
1325872		lesinhhung	Vrtić (COCI18_vrtic)	C++17	160 / 160	437 ms	33656 KiB

vrtic

#include <bits/stdc++.h>
using namespace std;

static const int INF = 1e9;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin >> n;
    vector<int> f(n + 1);
    for (int i = 1; i <= n; i++) cin >> f[i];

    vector<long long> candy(n + 1);
    for (int i = 1; i <= n; i++) cin >> candy[i];

    // Build undirected graph of the permutation (each component is a cycle)
    vector<vector<int>> g(n + 1);
    for (int i = 1; i <= n; i++) {
        int p = f[i];
        g[i].push_back(p);
        g[p].push_back(i);
    }

    // Sort candies, keep original bag indices
    vector<int> ord(n + 1);
    iota(ord.begin(), ord.end(), 0);
    sort(ord.begin() + 1, ord.end(), [&](int i, int j) {
        return candy[i] < candy[j];
    });

    vector<long long> val(n + 1);
    for (int pos = 1; pos <= n; pos++) val[pos] = candy[ord[pos]];

    // Find cycle components; groupBySize[len] stores representative nodes of cycles with that length
    vector<char> vis(n + 1, 0);
    vector<vector<int>> groupBySize(n + 1);
    vector<int> compSizeOfRoot; // not needed, but keep structure

    function<int(int)> dfsCount = [&](int u) -> int {
        vis[u] = 1;
        int cnt = 1;
        for (int v : g[u]) if (!vis[v]) cnt += dfsCount(v);
        return cnt;
    };

    vector<int> used(n + 1, 0);
    for (int i = 1; i <= n; i++) {
        if (!vis[i]) {
            int sz = dfsCount(i);
            groupBySize[sz].push_back(i);
            used[sz]++;
        }
    }

    // Collect distinct sizes
    vector<int> sizes;      // distinct cycle lengths
    vector<int> counts;     // how many cycles of that length
    for (int len = 1; len <= n; len++) {
        if (used[len] > 0) {
            sizes.push_back(len);
            counts.push_back(used[len]);
        }
    }
    int m = (int)sizes.size();

    // mixed radix bases and multipliers
    vector<int> base(m), pro(m, 1);
    long long limitLL = 1;
    for (int i = 0; i < m; i++) {
        base[i] = counts[i] + 1;
        limitLL *= base[i];
    }
    int limit = (int)limitLL; // in practice stays manageable for N<=150 (as in AC)
    for (int i = m - 2; i >= 0; i--) pro[i] = pro[i + 1] * base[i + 1];

    auto decode = [&](int x) {
        vector<int> v(m, 0);
        for (int i = m - 1; i >= 0; i--) {
            v[i] = x % base[i];
            x /= base[i];
        }
        return v;
    };

    // Precompute cost[l][r] for assigning sorted segment [l..r] to one cycle
    // cost formula matches AC: len=1 ->0, len=2 -> v[r]-v[l], len>=3 -> max(prev, v[r]-v[r-2])
    vector<vector<int>> cost(n + 2, vector<int>(n + 2, 0));
    for (int l = 1; l <= n; l++) {
        cost[l][l] = 0;
        for (int r = l + 1; r <= n; r++) {
            int len = r - l + 1;
            if (len == 2) {
                cost[l][r] = (int)min<long long>(INT_MAX, val[r] - val[l]);
            } else {
                cost[l][r] = cost[l][r - 1];
                long long diff2 = val[r] - val[r - 2];
                if (diff2 > cost[l][r]) cost[l][r] = (int)min<long long>(INT_MAX, diff2);
            }
        }
    }

    // DP over mixed-radix state: DP[state] = minimal possible maximal dissatisfaction so far
    vector<int> dp(limit, INF), trace(limit, -1);
    dp[0] = 0;

    for (int st = 0; st + 1 < limit; st++) {
        if (dp[st] >= INF) continue;
        vector<int> taken = decode(st);

        int lpos = 1;
        for (int i = 0; i < m; i++) lpos += taken[i] * sizes[i];

        for (int i = 0; i < m; i++) {
            if (taken[i] + 1 < base[i]) {
                int nst = st + pro[i];
                int len = sizes[i];
                int rpos = lpos + len - 1;
                int cand = max(dp[st], cost[lpos][rpos]);
                if (cand < dp[nst]) {
                    dp[nst] = cand;
                    trace[nst] = i;
                }
            }
        }
    }

    int best = dp[limit - 1];
    cout << best << "\n";

    // Reconstruct order of block lengths
    vector<int> blocks;
    int st = limit - 1;
    while (st > 0) {
        int i = trace[st];
        blocks.push_back(sizes[i]);
        st -= pro[i];
    }
    reverse(blocks.begin(), blocks.end());

    // Now assign actual positions (1..n in sorted candies) to each child vertex
    vector<int> idxPos(n + 1, 0);
    fill(vis.begin(), vis.end(), 0);

    function<void(int,int,int)> buildCycleAssign = [&](int u, int L, int R) {
        vis[u] = 1;
        for (int v : g[u]) {
            if (!vis[v]) {
                if ( ((idxPos[u] - L) & 1) ) {
                    idxPos[v] = idxPos[u] - 2;
                } else {
                    if (idxPos[u] + 2 <= R) idxPos[v] = idxPos[u] + 2;
                    else if (idxPos[u] < R) idxPos[v] = R;
                    else idxPos[v] = R - 1;
                }
                buildCycleAssign(v, L, R);
            }
        }
    };

    int curL = 1;
    for (int len : blocks) {
        int root = groupBySize[len].back();
        groupBySize[len].pop_back();

        idxPos[root] = curL;
        buildCycleAssign(root, curL, curL + len - 1);
        curL += len;
    }

    // Translate sorted-position -> bag index -> candy value for each child
    vector<long long> ans(n + 1);
    for (int i = 1; i <= n; i++) {
        int pos = idxPos[i];          // 1..n
        int bagIdx = ord[pos];        // original bag index
        ans[i] = candy[bagIdx];
    }

    for (int i = 1; i <= n; i++) {
        cout << ans[i] << (i == n ? '\n' : ' ');
    }
    return 0;
}

• Subtask 1: 16 / 16
• Subtask 2: 16 / 16
• Subtask 3: 16 / 16
• Subtask 4: 16 / 16
• Subtask 5: 16 / 16
• Subtask 6: 16 / 16
• Subtask 7: 16 / 16
• Subtask 8: 16 / 16
• Subtask 9: 16 / 16
• Subtask 10: 16 / 16