1 条题解
-
0
#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
- 上传者