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...