Submission #1129360

#	Time	Username	Problem	Language	Result	Execution time	Memory
1129360		Kerim	Friends (BOI17_friends)	C++20	100 / 100	348 ms	1924 KiB

friends

#include <bits/stdc++.h>

using namespace std;

const int MAX_N = 2500;
int n;
vector <int> adj[MAX_N];
unordered_map <int, bool> isAdj[MAX_N];
set <int> solution, group[MAX_N];
vector <int> frecv[MAX_N];
bool vis[MAX_N];

void findGroup( multiset <int> candidates, set<int> uniqueCandidates, set <int> chosen, int p, int q ) {
    if ( uniqueCandidates.size() > p + q )
        return;

    if ( candidates.size() == 0 ) {
        if ( chosen.size() > solution.size() )
            solution = chosen;
        return;
    }

    int v = *candidates.begin();
    if ( p > 0 ) {
        multiset <int> newCandidates = candidates;
        set<int> newUniqueCandidates = uniqueCandidates;
        set <int> newChosen = chosen;
        newCandidates.erase( v );
        newUniqueCandidates.erase( v );
        newChosen.insert( v );
        for ( int u: adj[v] ) {
            if ( chosen.find( u ) == chosen.end() ) {
                newCandidates.insert( u );
                newUniqueCandidates.insert( u );
            }
        }
        findGroup( newCandidates, newUniqueCandidates, newChosen, p - 1, q );
    }

    if ( q > 0 ) {
        multiset <int> newCandidates = candidates;
        set<int> newUniqueCandidates = uniqueCandidates;
        set <int> newChosen = chosen;
        newCandidates.erase( newCandidates.lower_bound( v ) );
        if ( newCandidates.find( v ) == newCandidates.end() )
            newUniqueCandidates.erase( v );
        findGroup( newCandidates, newUniqueCandidates, newChosen, p, q - 1 );
    }
}

bool verif() {
    for ( int v = 0; v < n; v++ ) {
        if ( frecv[v].size() > 1 )
            return false;
    }
    return true;
}

bool check( set <int> a, int q ) {
    for ( int v: a ) {
        for ( int u: adj[v] ) {
            if ( a.find( u ) == a.end() )
                q--;
        }
    }
    return (q >= 0);
}

int main() {
    int p, q;

    cin >> n >> p >> q;
    for ( int u = 0; u < n; u++ ) {
        int k;
        cin >> k;
        for ( int i = 0; i < k; i++ ) {
            int v;
            cin >> v;
            adj[u].push_back( v );
            isAdj[u][v] = true;
        }
    }
    for ( int u = 0; u < n; u++ ) {
        if ( adj[u].size() > p + q - 1 ) {
            cout << "detention\n";
            return 0;
        }
        for ( int v: adj[u] ) {
            if ( (isAdj[u][v] ^ isAdj[v][u]) == 1 ) {
                cout << "detention\n";
                return 0;
            }
        }
    }

    for ( int u = 0; u < n; u++ ) {
        if ( vis[u] )
            continue;

        multiset <int> candidates;
        set<int> uniqueCandidates;
        set <int> chosen;
        candidates.insert( u );
        uniqueCandidates.insert( u );
        solution.clear();
        findGroup( candidates, uniqueCandidates, chosen, p, q );
        if ( solution.size() == 0 ) {
            cout << "detention\n";
            return 0;
        }
        for ( int v: solution ) {
            vis[v] = true;
            frecv[v].push_back( u );
            group[u].insert( v );
        }
    }

    while ( !verif() ) {
        int x, y;
        for ( int v = 0; v < n; v++ ) {
            if ( frecv[v].size() > 1 ) {
                x = frecv[v][0], y = frecv[v][1];
                break;
            }
        }

        set <int> a = group[x], b = group[y];
        set <int> a1 = a, b1 = b;
        for ( int v: b1 )
            a1.erase( v );
        set <int> a2 = a, b2 = b;
        for ( int v: a2 )
            b2.erase( v );

        if ( check( a1, q ) ) {
            group[x] = a1;
            group[y] = b1;
        } else if ( check( b2, q ) ) {
            group[x] = a2;
            group[y] = b2;
        }


        for ( int v = 0; v < n; v++ )
            frecv[v].clear();
        for ( int u = 0; u < n; u++ ) {
            for ( int v: group[u] )
                frecv[v].push_back( u );
        }
    }

    int ans = 0;
    for ( int u = 0; u < n; u++ ) {
        if ( group[u].size() > 0 )
            ans++;
    }

    cout << "home\n";
    cout << ans << "\n";
    for ( int u = 0; u < n; u++ ) {
        if ( group[u].size() == 0 )
            continue;

        cout << group[u].size() << " ";
        for ( int v: group[u] )
            cout << v << " ";
        cout << "\n";
    }

    return 0;
}

• Subtask 1: 20 / 20
• Subtask 2: 37 / 37
• Subtask 3: 12 / 12
• Subtask 4: 31 / 31