Submission #813316

#	Time	Username	Problem	Language	Result	Execution time	Memory
813316		vjudge1	Bosses (BOI16_bosses)	C++17	0 / 100	0 ms	212 KiB

bosses

// Always have faith in greedy.

#include <bits/stdc++.h>

using namespace std;

int n;
vector<vector<int>> acParents, acChildren;
vector<int> nodes;
vector<int> parent;
vector<vector<int>> adjList;
int r = -1;

int depthFirstSearch(const int& u, const int& p, const int& d)
{
    int result = d;
    for (auto &v : adjList[u])
        result += depthFirstSearch(v, u, d + 1);
    return result;
}

int main()
{
    // freopen("inp.txt", "r", stdin);

    ios::sync_with_stdio(false);

    cin >> n;
    acParents.resize(n + 1);
    acChildren.resize(n + 1);
    for (int size, v, u = 1; u <= n; u++)
    {
        cin >> size;
        while (size --> 0)
        {
            cin >> v;
            acParents[u].push_back(v);
            acChildren[v].push_back(u);
        }
    }

    nodes.resize(n);
    iota(nodes.begin(), nodes.end(), 1);

    for (int u = 1; u <= n && r == -1; u++)
        if (acParents[u].empty())
            r = u;

    if (r != -1)
    {
        swap(nodes[0], nodes[r - 1]);
        sort(nodes.begin() + 1, nodes.end(), [&](const int& u, const int& v) -> bool {
            return acChildren[u].size() > acChildren[v].size();
        });
    }
    else
    {
        sort(nodes.begin(), nodes.end(), [&](const int& u, const int& v) -> bool {
            return acChildren[u].size() > acChildren[v].size();
        });
    }

    parent.resize(n + 1, -1);
    adjList.resize(n + 1);

    for (auto &u: nodes)
    {
        if (r == -1) r = u;
        for (auto &v : acChildren[u])
        {
            if (parent[v] != -1 || v == r) continue;
            parent[v] = u;
            adjList[u].push_back(v);
        }
    }

    cout << depthFirstSearch(r, -1, 1);
}

• Subtask 1: 0 / 22
• Subtask 2: 0 / 45
• Subtask 3: 0 / 33