Submission #208543

#	Time	Username	Problem	Language	Result	Execution time	Memory
208543		eriksuenderhauf	Friends (BOI17_friends)	C++11	20 / 100	1048 ms	1528 KiB

friends

//#pragma GCC optimize("O3")
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define enl printf("\n")
#define case(t) printf("Case #%d: ", (t))
#define ni(n) scanf("%d", &(n))
#define nl(n) scanf("%lld", &(n))
#define nai(a, n) for (int i = 0; i < (n); i++) ni(a[i])
#define nal(a, n) for (int i = 0; i < (n); i++) nl(a[i])
#define pri(n) printf("%d\n", (n))
#define prl(n) printf("%lld\n", (n))
#define pii pair<int, int>
#define pil pair<int, long long>
#define pll pair<long long, long long>
#define vii vector<pii>
#define vil vector<pil>
#define vll vector<pll>
#define vi vector<int>
#define vl vector<long long>
#define pb push_back
#define mp make_pair
#define fi first
#define se second
using namespace std;
using namespace __gnu_pbds;
typedef long long ll;
typedef cc_hash_table<int,null_type,hash<int>> ht;
typedef tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update> oset;
const double pi = acos(-1);
const int MOD = 1e9 + 7;
const int INF = 1e9 + 7;
const int MAXN = 3e3 + 5;
const double eps = 1e-9;
bool mrk[MAXN][MAXN];
vi adj[MAXN];
ht arr[MAXN];
int n, p, q;

bool valid(ht& a) {
    if ((int)a.size() > p) return false;
    int cnt = 0;
    for (auto it: a) {
        for (int v: adj[it]) {
            if (a.find(v) != a.end())
                continue;
            cnt++;
            if (cnt > q) return false;
        }
    }
    return (cnt <= q);
}

void dfs(int u, ht& in, int root) {
    if (!arr[root].empty() || (int)in.size() > p) return;
    if ((int)in.size() <= p && valid(in)) {
        arr[root] = in;
        return;
    }
    for (auto it: in) {
        for (int v: adj[it]) {
            if (in.find(v) != in.end() || adj[v].size() > p + q)
                continue;
            in.insert(v);
            dfs(v, in, root);
            if (!arr[root].empty())
                return;
            in.erase(v);
        }
    }
}

int main() {
    assert(3 == scanf("%d %d %d", &n, &p, &q));
    int cnt = 0;
    for (int i = 0; i < n; i++) {
    	int d;
    	assert(1 == scanf("%d", &d));
    	for (int j = 0; j < d; j++) {
    		int u;
            assert(1 == scanf("%d", &u));
    		adj[i].pb(u);
            if (mrk[u][i]) mrk[i][u] = mrk[u][i];
            else mrk[i][u] = ++cnt;
    	}
    }
    for (int i = 0; i < n; i++)
    	for (int j = 0; j < n; j++)
    		if ((mrk[i][j] && !mrk[j][i]) || (mrk[j][i] && !mrk[i][j])) {
    			printf("detention\n");
                return 0;
            }
    for (int i = 0; i < n; i++) {
    	ht in; in.insert(i);
        dfs(i, in, i);
    	if (arr[i].empty()) {
    		printf("detention\n");
            return 0;
        }
    }
    for (int i = 0; i < n; i++) {
    	for (int j = i + 1; j < n; j++) {
            ht a = arr[j];
            for (auto it: arr[i])
                if (a.find(it) != a.end())
                    a.erase(it);
            if (valid(a)) {
                arr[j] = a;
                continue;
            }
            a = arr[i];
            for (auto it: arr[j])
                if (a.find(it) != a.end())
                    a.erase(it);
            arr[i] = a;
    	}
    }
    printf("home\n");
    cnt = n;
    for (int i = 0; i < n; i++) if (arr[i].empty()) cnt--;
    printf("%d\n", cnt);
    for (int i = 0; i < n; i++) {
        if (arr[i].empty()) continue;
        printf("%d ", (int)arr[i].size());
        for (int j: arr[i])
            printf("%d ", j);
        printf("\n");
    }
}

Compilation message (stderr)

friends.cpp: In function 'void dfs(int, ht&, int)':
friends.cpp:62:57: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             if (in.find(v) != in.end() || adj[v].size() > p + q)
                                           ~~~~~~~~~~~~~~^~~~~~~

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