Submission #762843

#TimeUsernameProblemLanguageResultExecution timeMemory
762843ThegeekKnight16Political Development (BOI17_politicaldevelopment)C++17
100 / 100
314 ms29000 KiB
#include <bits/stdc++.h> using namespace std; const int MAXN = 5e4 + 10; const int INF = 0x3f3f3f3f; set<pair<int, int> > verts; array<set<int>, MAXN> grafo; vector<int> active; int grau[MAXN]; int resp = 0; void bt(set<int>::iterator it, int v) { if (it == grafo[v].end()) { resp = max(resp, (int)active.size()+1); return; } // cerr << *it << '\n'; auto aux = it; bt(++aux, v); for (auto viz : active) if (grafo[*it].find(viz) == grafo[*it].end()) return; active.push_back(*it); aux = it; bt(++aux, v); active.pop_back(); } int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); int N, K; cin >> N >> K; for (int i = 0; i < N; i++) { cin >> grau[i]; for (int j = 0; j < grau[i]; j++) { int X; cin >> X; grafo[i].insert(X); } verts.emplace(grau[i], i); } while (!verts.empty()) { // for (auto [g, id] : verts) cerr << "||" << g << " " << id << " "; // cerr << '\n'; int cur = verts.begin()->second; verts.erase(verts.begin()); bt(grafo[cur].begin(), cur); for (auto viz : grafo[cur]) { grafo[viz].erase(cur); verts.erase(make_pair(grau[viz], viz)); grau[viz]--; verts.emplace(grau[viz], viz); } grafo[cur].clear(); grau[cur] = INF; } cout << resp << '\n'; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...