답안 #945159

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
945159 2024-03-13T13:09:19 Z LucaIlie Friends (BOI17_friends) C++17
0 / 100
3 ms 860 KB
#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";
            cout << u << "\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;
}

Compilation message

friends.cpp: In function 'void findGroup(std::multiset<int>, std::set<int>, std::set<int>, int, int)':
friends.cpp:14:34: warning: comparison of integer expressions of different signedness: 'std::set<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   14 |     if ( uniqueCandidates.size() > p + q )
      |          ~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~
friends.cpp: In function 'int main()':
friends.cpp:84:28: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   84 |         if ( adj[u].size() > p + q - 1 ) {
      |              ~~~~~~~~~~~~~~^~~~~~~~~~~
friends.cpp:120:16: warning: 'y' may be used uninitialized in this function [-Wmaybe-uninitialized]
  120 |         int x, y;
      |                ^
friends.cpp:120:13: warning: 'x' may be used uninitialized in this function [-Wmaybe-uninitialized]
  120 |         int x, y;
      |             ^
# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 600 KB Output is correct
2 Correct 0 ms 600 KB Output is correct
3 Correct 1 ms 604 KB Output is correct
4 Correct 1 ms 604 KB Output is correct
5 Correct 0 ms 856 KB Output is correct
6 Incorrect 1 ms 600 KB Extra information in the output file
7 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 600 KB Output is correct
2 Correct 3 ms 860 KB Output is correct
3 Correct 1 ms 860 KB Output is correct
4 Incorrect 1 ms 860 KB Extra information in the output file
5 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 600 KB Output is correct
2 Correct 3 ms 860 KB Output is correct
3 Correct 1 ms 860 KB Output is correct
4 Incorrect 1 ms 860 KB Extra information in the output file
5 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 600 KB Output is correct
2 Correct 0 ms 600 KB Output is correct
3 Correct 1 ms 604 KB Output is correct
4 Correct 1 ms 604 KB Output is correct
5 Correct 0 ms 856 KB Output is correct
6 Incorrect 1 ms 600 KB Extra information in the output file
7 Halted 0 ms 0 KB -