Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- /*
- Доказательство условия про два ребра:
- - inB[v] + inC[v] считаем только по "живым" годам.
- - Замечание: когда алгоритм закончился, для любой вершины
- inB[v] == 1 и inC[v] == 1.
- - Действительно, исходящих рёбер каждого цвета ровно |V|,
- а условие задачи требует ≥1 входа каждого цвета;
- - поэтому два входа одного цвета в одну вершину невозможны.
- */
- /*************************************************************
- * Для каждого года i есть два ориентированных ребра
- * Ai ──(blue)──► Bi
- * Ai ──(red) ─► Ci
- *
- * Оставляем подмножество лет S. Требование условия:
- *
- * в каждую вершину входит ≥ 1 blue-и ≥ 1 red-ребро.
- * Поэтому в корректном ответе в вершину не может
- * входить два ребра одного цвета – иначе какой-то
- * вершине не хватило бы входов (принцип Дирихле).
- *
- * Алгоритм “листопад”.
- * ------------------------------------
- * • inB[v], inC[v] –- число blue/red входов из ещё
- * «живых» лет;
- * • occCnt[v] – число «живых» лет,
- * где v встречается в A,B или C.
- * • Очередь Q из вершин, у которых inB==0 || inC==0.
- * • Пока Q не пуста:
- * v = pop()
- * если occCnt[v] == 0 continue
- * для каждого года idx, где v встречается
- * if removed[idx] continue
- * removed[idx] = true
- * --occCnt[ Aidx ], occCnt[ Bidx ], occCnt[ Cidx ]
- * --inB[ Bidx ], --inC[ Cidx ];
- * если какая-то вершина осталась без входа
- * ⇒ push в очередь
- * ответ = удаленные года.
- * Работает O(N) памяти/времени:
- * каждый год и вершина обрабатываются максимум один раз.
- *************************************************************/
- #include <bits/stdc++.h>
- using namespace std;
- struct Triple { int a, b, c; };
- int main() {
- ios::sync_with_stdio(false);
- cin.tie(nullptr);
- int N;
- if (!(cin >> N)) return 0;
- vector<Triple> yr(N);
- for (int i = 0; i < N; ++i) cin >> yr[i].a;
- for (int i = 0; i < N; ++i) cin >> yr[i].b;
- for (int i = 0; i < N; ++i) cin >> yr[i].c;
- const int SZ = N + 1; // вершины 1..N
- vector<int> inB(SZ, 0), inC(SZ, 0), occCnt(SZ, 0);
- vector<vector<int>> occ(SZ); // годы, где встречается вершина
- // собираем "статистику"
- for (int i = 0; i < N; ++i) {
- auto [a,b,c] = yr[i];
- ++inB[b]; ++inC[c];
- for (int v : {a,b,c}) {
- ++occCnt[v];
- occ[v].push_back(i);
- }
- }
- queue<int> Q;
- vector<char> inQ(SZ, 0);
- auto push_if_bad = [&](int v) {
- if (occCnt[v] && (inB[v]==0 || inC[v]==0) && !inQ[v]) {
- Q.push(v); inQ[v] = 1;
- }
- };
- for (int v = 1; v <= N; ++v) push_if_bad(v);
- vector<char> removedYr(N, 0);
- int removedCnt = 0;
- while (!Q.empty()) {
- int v = Q.front(); Q.pop(); inQ[v] = 0;
- if (occCnt[v]==0) continue;
- // могла обнулиться раньше
- for (int idx : occ[v]) {
- if (removedYr[idx]) continue;
- removedYr[idx] = 1;
- ++removedCnt;
- auto [a,b,c] = yr[idx];
- // убрали год – вершины в нём проявляются на год меньше */
- for (int u : {a,b,c}) {
- if (--occCnt[u]==0) inQ[u]=0;
- // совсем исчезла
- }
- // у целей ушёл вход
- if (--inB[b]==0) push_if_bad(b);
- if (--inC[c]==0) push_if_bad(c);
- }
- }
- cout << removedCnt << '\n';
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement
