1 条题解

  • 0
    @ 2026-5-2 20:32:14
    #include <bits/stdc++.h>
    #define inf INT32_MAX / 2
    using namespace std;
    
    const int MN = 1e5 + 3;
    int n, m, tot;
    int rec[MN], siz[MN], nxr[MN], ans[MN];
    set<int> st[MN];
    
    int main() {
        ios::sync_with_stdio(0);
        cin.tie(0), cout.tie(0);
    
        cin >> n >> m;
        for (int i = 1; i <= n; i++) {
            st[0].insert(i);
            ans[i] = inf;
        }
        siz[0] = n;
    
        for (int i = 1, k; i <= m; i++) {
            cin >> k;
            vector<int> chg, clr;
    
            for (int j = 1, x; j <= k; j++) {
                cin >> x;
                if (!nxr[rec[x]]) nxr[rec[x]] = ++tot;
    
                siz[rec[x]]--;
                st[rec[x]].erase(x);
                chg.push_back(rec[x]);
                clr.push_back(rec[x]);
    
                siz[nxr[rec[x]]]++;
                st[nxr[rec[x]]].insert(x);
                chg.push_back(nxr[rec[x]]);
                rec[x] = nxr[rec[x]];
                // nxr[rec[x]] = 0;
            }
            for (int j : clr) nxr[j] = 0;
            for (int j : chg) {
                int x = *st[j].begin();
                if (siz[j] == 1) ans[x] = min(ans[x], i);
            }
        }
    
        for (int i = 1; i <= n; i++) cout << (ans[i] == inf ? 0 : ans[i]) << " ";
        return 0;
    }
    
    • 1

    信息

    ID
    10356
    时间
    1000ms
    内存
    256MiB
    难度
    10
    标签
    递交数
    1
    已通过
    1
    上传者