Submission #521382

#	Time	Username	Problem	Language	Result	Execution time	Memory
521382		Yazan_Alattar	Friends (BOI17_friends)	C++14	100 / 100	150 ms	8144 KiB

friends

#include <iostream>
#include <fstream>
#include <vector>
#include <cstring>
#include <algorithm>
#include <set>
#include <map>
#include <queue>
#include <list>
#include <stack>
#include <utility>
#include <cmath>
#include <numeric>
#include <assert.h>
using namespace std;
typedef long long ll;
#define F first
#define S second
#define pb push_back
#define endl "\n"
#define all(x) x.begin(), x.end()
const int M = 3007;
const ll inf = 1e18;
const ll mod = 1e9 + 7;
const double pi = acos(-1);
const int dx[] = {1, 0, -1, 0}, dy[] = {0, 1, 0, -1};

void close(){ cout << "detention" << endl; exit(0); }

stack <int> stk;
vector <int> adj[M], group[M], cur;
int n, P, Q, in[M], out[M];
bool vist[M], frnd[M][M];

bool valid(vector <int> v)
{
    int q = 0;
    for(auto i : v) vist[i] = 1;
    for(auto i : v) for(auto j : adj[i]) if(!vist[j]) ++q;
    for(auto i : v) vist[i] = 0;
    return (v.size() <= P && q <= Q);
}

void get(int source, int p, int q, bool add)
{
    if(!group[source].empty() || p > P || q > Q || p + q + stk.size() > P + Q) return;
    if(stk.empty()){
        group[source] = cur;
        return;
    }
    int node = stk.top();
    stk.pop();
    if(add){
        in[node] = 1;
        cur.pb(node);
        vector <int> neighbores;
        for(auto i : adj[node]){
            if(!vist[i]){
                neighbores.pb(i);
                stk.push(i);
                vist[i] = 1;
            }
            q += out[i];
        }
        get(source, p + 1, q, 0);
        if(group[source].empty()) get(source, p + 1, q, 1);
        for(auto i : neighbores){
            vist[i] = 0;
            stk.pop();
        }
        for(auto i : adj[node]) q -= out[i];
        cur.pop_back();
        in[node] = 0;
    }
    else{
        out[node] = 1;
        vector <int> neighbores;
        for(auto i : adj[node]) q += in[i];
        get(source, p, q, 0);
        if(group[source].empty())get(source, p, q, 1);
        for(auto i : neighbores){
            vist[i] = 0;
            stk.pop();
        }
        for(auto i : adj[node]) q -= in[i];
        out[node] = 0;
    }
    stk.push(node);
    return;
}

int main()
{
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    cin >> n >> P >> Q;
    for(int i = 1; i <= n; ++i){
        int m;
        cin >> m;
        for(int j = 1; j <= m; ++j){
            int x;
            cin >> x; ++x;
            adj[i].pb(x);
            frnd[i][x] = 1;
        }
    }
    for(int i = 1; i <= n; ++i) for(int j = i + 1; j <= n; ++j) if(frnd[i][j] != frnd[j][i]) close();
    for(int i = 1; i <= n; ++i){
        stk.push(i);
        vist[i] = 1;
        get(i, 0, 0, 1);
        vist[i] = 0;
        stk.pop();
        if(group[i].empty()) close();
    }
    for(int i = 1; i <= n; ++i){
        for(int j = i + 1; j <= n; ++j){
            vector <int> xi, xj, yi, yj;
            bool ins = 0;
            for(auto k : group[i]) in[k] = 0;
            for(auto k : group[j]) in[k] = 0;
            for(auto k : group[i]) in[k] |= 1;
            for(auto k : group[j]) in[k] |= 2, ins |= (in[k] == 3);
            if(!ins) continue;
            for(auto k : group[i]){
                if(in[k] == 1){
                    xi.pb(k);
                    xj.pb(k);
                }
                else yj.pb(k);
            }
            for(auto k : group[j]){
                if(in[k] == 2){
                    yi.pb(k);
                    yj.pb(k);
                }
                else xi.pb(k);
            }
            if(valid(xi) && valid(yi)){
                swap(group[i], xi);
                swap(group[j], yi);
            }
            else{
                swap(group[i], xj);
                swap(group[j], yj);
            }
        }
    }
    cout << "home\n";
    vector < vector <int> > ans;
    for(int i = 1; i <= n; ++i) if(group[i].size()){
        vector <int> v;
        for(auto j : group[i]) v.pb(j);
        ans.pb(v);
    }
    cout << ans.size() << endl;
    for(auto i : ans){
        cout << i.size() << " ";
        for(auto j : i) cout << j - 1 << " ";
        cout << endl;
    }
    return 0;
}

Compilation message (stderr)

friends.cpp: In function 'bool valid(std::vector<int>)':
friends.cpp:41:22: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   41 |     return (v.size() <= P && q <= Q);
      |             ~~~~~~~~~^~~~
friends.cpp: In function 'void get(int, int, int, bool)':
friends.cpp:46:71: warning: comparison of integer expressions of different signedness: 'std::stack<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   46 |     if(!group[source].empty() || p > P || q > Q || p + q + stk.size() > P + Q) return;
      |                                                    ~~~~~~~~~~~~~~~~~~~^~~~~~~

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