Submission #945065

#	Time	Username	Problem	Language	Result	Execution time	Memory
945065		LucaIlie	Friends (BOI17_friends)	C++17	0 / 100	1089 ms	860 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( set<int> candidates, set<int> chosen, set<int> refused, int p, int q ) {
    /*cout << "stare\n";
    cout << "sz ";
    cout << candidates.size() << "\n";
    for ( int v: candidates )
        cout << v << " ";
    cout << "\n";
    cout << "sz ";
    cout << chosen.size() << "\n";
    for ( int v: chosen )
        cout << v << " ";
    cout << "\n";
    cout << "sz ";
    cout << refused.size() << "\n";
    for ( int v: refused )
        cout << v << " ";
    cout << "\n";
    cout << "\n\n";*/
    if ( candidates.size() == 0 ) {
        if ( chosen.size() > solution.size() )
            solution = chosen;
        return;
    }

    if ( candidates.size() > p + q )
        return;

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

        if ( q > 0 ) {
            set <int> newCandidates = candidates, newChosen = chosen, newRefused = refused;
            newCandidates.erase( v );
            newRefused.insert( v );
            findGroup( newCandidates, newChosen, newRefused, 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 ) {
    set<int> c;
    for ( int v: a ) {
        for ( int u: adj[v] )
            c.insert( u );
    }
    return (c.size() - a.size() <= q);
}

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;

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

    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 {
            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: solution )
                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;
}

Compilation message (stderr)

friends.cpp: In function 'void findGroup(std::set<int>, std::set<int>, std::set<int>, int, int)':
friends.cpp:37:28: warning: comparison of integer expressions of different signedness: 'std::set<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   37 |     if ( candidates.size() > p + q )
      |          ~~~~~~~~~~~~~~~~~~^~~~~~~
friends.cpp: In function 'bool check(std::set<int>, int)':
friends.cpp:75:33: warning: comparison of integer expressions of different signedness: 'std::set<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   75 |     return (c.size() - a.size() <= q);
      |             ~~~~~~~~~~~~~~~~~~~~^~~~
friends.cpp: In function 'int main()':
friends.cpp:93:28: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   93 |         if ( adj[u].size() > p + q - 1 ) {
      |              ~~~~~~~~~~~~~~^~~~~~~~~~~
friends.cpp:128:16: warning: 'y' may be used uninitialized in this function [-Wmaybe-uninitialized]
  128 |         int x, y;
      |                ^
friends.cpp:128:13: warning: 'x' may be used uninitialized in this function [-Wmaybe-uninitialized]
  128 |         int x, y;
      |             ^

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