Submission #1088458

#	Time	Username	Problem	Language	Result	Execution time	Memory
1088458		gyg	Friends (BOI17_friends)	C++17	100 / 100	952 ms	2776 KiB

friends

#pragma GCC optimize("Ofast", "unroll-loops")
#pragma GCC target("avx2")
#include <bits/stdc++.h>
using namespace std;
#define arr array
#define vct vector
#define hset unordered_set
#define pii pair<int, int>
const int MAX_N = 2500 + 5;

int n, p, q;
arr<hset<int>, MAX_N> adj;

bool vld(hset<int>& x) {
    if (x.size() > p) return false;
    int cnt = 0;
    for (int u : x) {
        for (int v : adj[u]) {
            cnt += (!x.count(v));
            if (cnt > q) return false;
        }
    }
    return true;
}

bool chck() {
    for (int u = 0; u < n; u++) 
        for (int v : adj[u])
            if (!adj[v].count(u)) return true;
    return false;
}

int cnt;
hset<int> inc, exc, ngh;
arr<hset<int>, MAX_N> grp;
void bcktr(int u) {
    if (grp[u].size()) return;
    if (inc.size() > p) return;
    if (cnt > q) return;
    if (ngh.size() + inc.size() + cnt > p + q) return;
    if (ngh.empty()) { grp[u] = inc; return; }

    int v = *ngh.begin();
    
    inc.insert(v), ngh.erase(v);
    vct<int> ins;
    for (int w : adj[v])    
        if (!(inc.count(w) || exc.count(w) || ngh.count(w))) ins.push_back(w), ngh.insert(w);
    int ch_cnt1 = 0;
    for (int w : exc) ch_cnt1 += (adj[v].count(w));
    cnt += ch_cnt1;
    bcktr(u);
    inc.erase(v), ngh.insert(v);
    for (int w : ins) ngh.erase(w);
    cnt -= ch_cnt1;

    if (grp[u].size()) return;

    int ch_cnt2 = 0;
    for (int w : inc) ch_cnt2 += (adj[w].count(v));
    cnt += ch_cnt2;
    ngh.erase(v), exc.insert(v);
    bcktr(u);
    cnt -= ch_cnt2;
    ngh.insert(v), exc.erase(v);
}
arr<vct<pii>, MAX_N> ext;
bool prcmp() {
    for (int u = 0; u < n; u++) {
        cnt = 0, inc = {u}, exc.clear(), ngh = adj[u];
        bcktr(u);
        if (grp[u].empty()) return true;
        for (int v : grp[u])
            for (int w : adj[v])
                if (!grp[u].count(w)) ext[u].push_back({v, w});
    }
    return false;
}

hset<int> mns(hset<int>& x, hset<int>& y) {
    hset<int> ans;
    for (int z : x)
        if (!y.count(z)) ans.insert(z);
    return ans;
}

void rslv(int u, int v) {
    hset<int> umv = mns(grp[u], grp[v]), vmu = mns(grp[v], grp[u]);
    if (grp[u] == umv) return;
  
    int i = 0, j = 0, k = 0, l = 0;
    for (pii& x : ext[u]) {
        if (umv.count(x.first)) i++;
        else if (grp[v].count(x.second)) j++;
    }
    for (pii& x : ext[v]) {
        if (vmu.count(x.first)) k++;
        else if (grp[u].count(x.second)) l++;
    }
    
    if (i + l <= q) grp[u] = umv;
    else grp[v] = vmu;
}

int main() {
    // freopen("fr.in", "r", stdin);
    cin >> n >> p >> q;
    for (int u = 0; u < n; u++) {
        int x; cin >> x;
        for (int i = 1; i <= x; i++) {
            int v; cin >> v;
            adj[u].insert(v);
        }
    }

    if (chck()) { cout << "detention" << endl; exit(0); }
    if (prcmp()) { cout << "detention" << endl; exit(0); }
    
    for (int u = 0; u < n; u++) {
        for (int v = u + 1; v < n; v++) {
            if (u == v) continue;
            rslv(u, v);
        }
    }

    vct<hset<int>> ans;
    for (int u = 0; u < n; u++)
        if (!grp[u].empty()) ans.push_back(grp[u]);

    cout << "home" << endl;
    cout << ans.size() << endl;
    for (hset<int> x : ans) {
        cout << x.size() << " ";
        for (int y : x) cout << y << " ";
        cout << endl;
    }
}

Compilation message (stderr)

friends.cpp: In function 'bool vld(std::unordered_set<int>&)':
friends.cpp:15:18: warning: comparison of integer expressions of different signedness: 'std::unordered_set<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   15 |     if (x.size() > p) return false;
      |         ~~~~~~~~~^~~
friends.cpp: In function 'void bcktr(int)':
friends.cpp:38:20: warning: comparison of integer expressions of different signedness: 'std::unordered_set<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   38 |     if (inc.size() > p) return;
      |         ~~~~~~~~~~~^~~
friends.cpp:40:39: warning: comparison of integer expressions of different signedness: 'std::unordered_set<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   40 |     if (ngh.size() + inc.size() + cnt > p + q) return;
      |         ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~

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