Submission

Score: 0

User: pxsit

Problemset: ร้านปลอดภาษี (Duty Free)

Language: cpp

Time: 0.000 second

Submitted On: 2026-06-01 12:17:30

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

struct DSU {
    int timer = 1;
    vector<int> head, lazy;

    DSU(int s) {
        // Allocate once
        head.resize(s + 9);
        lazy.resize(s + 9, 0);
    }

    // Iterative findhead with path compression to prevent stack overhead
    int findhead(int n) {
        int root = n;
        while (true) {
            if (lazy[root] != timer) {
                lazy[root] = timer;
                head[root] = root;
            }
            if (head[root] == root) break;
            root = head[root];
        }
        
        // Path compression
        int curr = n;
        while (curr != root) {
            int nxt = head[curr];
            head[curr] = root;
            curr = nxt;
        }
        return root;
    }

    bool merge(int a, int b) {
        int ha = findhead(a), hb = findhead(b);
        if (ha == hb) return false;
        head[ha] = hb;
        return true;
    }

    void reset() {
        timer++;
    }
};

int minimum_bag_rearrangement_time(const vector<int>& vec) {
    int ans = 0;
    int n = vec.size();
    DSU dsu(n);
    
    for (int x : vec) {
        int h = dsu.findhead(x);
        if (h == 0) {
            dsu.reset();
            ans++;
            h = dsu.findhead(x); // Re-run after reset
        }
        dsu.merge(h, h - 1);
    }
    return ans;
}