Submission #133356

#	Time	Username	Problem	Language	Result	Execution time	Memory
133356		imeimi2000	Friends (BOI17_friends)	C++17	100 / 100	340 ms	11236 KiB

friends

#include <iostream>
#include <algorithm>
#include <vector>
#include <cstdlib>

using namespace std;
typedef long long llong;

void fail() {
    printf("detention\n");
    exit(0);
}

int n, p, q;
vector<int> edge[2500];
int con[2500][2500];
vector<int> group[2500];

bool in[2500];
bool ex[2500];
bool backtrack(vector<int> &ret, int it = 0, int jt = 0, int np = 1, int nq = 0) {
    if (p < np || q < nq) return 0;
    while (it < ret.size()) {
        while (jt < edge[ret[it]].size()) {
            int x = edge[ret[it]][jt++];
            if (!in[x] && !ex[x]) {
                {
                    int nxp = np, nxq = nq;
                    in[x] = 1;
                    ret.push_back(x);
                    ++nxp;
                    for (int i : edge[x]) {
                        if (ex[i]) ++nxq;
                    }
                    if (backtrack(ret, it, jt, nxp, nxq))
                        return 1;
                    in[x] = 0;
                    ret.pop_back();
                }
                {
                    int nxp = np, nxq = nq;
                    ex[x] = 1;
                    for (int i : edge[x]) {
                        if (in[i]) ++nxq;
                    }
                    if (backtrack(ret, it, jt, nxp, nxq))
                        return 1;
                    ex[x] = 0;
                }
                return 0;
            }
        }
        ++it;
        jt = 0;
    }
    return 1;
}

void pre_process() {
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j)
            in[j] = ex[j] = 0;
        in[i] = 1;
        group[i].push_back(i);
        if (!backtrack(group[i])) fail();
    }
}

int st[2500];
void solve() {
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < i; ++j) {
            for (int k : group[i]) st[k] |= 1;
            vector<int> gs;
            for (int k : group[j]) {
                st[k] |= 2;
                if (st[k] == 3) gs.push_back(k);
            }
            int c1 = 0, c2 = 0;
            for (int k : gs) {
                for (int l : edge[k]) {
                    if (st[l] == 1) ++c1;
                    if (st[l] == 2) ++c2;
                }
            }
            if (c1 < c2) {
                vector<int> ns;
                for (int k : group[i]) if (st[k] == 1)
                    ns.push_back(k);
                group[i] = ns;
            }
            else {
                vector<int> ns;
                for (int k : group[j]) if (st[k] == 2)
                    ns.push_back(k);
                group[j] = ns;
            }
            for (int k : group[i]) st[k] = 0;
            for (int k : group[j]) st[k] = 0;
        }
    }
}

int main() {
    ios_base::sync_with_stdio(0); cin.tie(0);
    cin >> n >> p >> q;
    {
        int one_cnt = 0;
        for (int i = 0; i < n; ++i) {
            int k;
            cin >> k;
            while (k--) {
                int x;
                cin >> x;
                if (con[i][x] == 1) --one_cnt;
                if (++con[i][x] == 1) ++one_cnt;
                ++con[x][i];
                edge[i].push_back(x);
            }
        }
        if (one_cnt > 0) fail();
    }
    for (int i = 0; i < n; ++i) {
        if (p + q <= edge[i].size()) fail();
    }
    pre_process();
    solve();
    printf("home\n");
    int cnt = 0;
    for (int i = 0; i < n; ++i) if (!group[i].empty())
        ++cnt;
    printf("%d\n", cnt);
    for (int i = 0; i < n; ++i) {
        if (group[i].empty()) continue;
        sort(group[i].begin(), group[i].end());
        printf("%u", group[i].size());
        for (int j : group[i]) printf(" %d", j);
        printf("\n");
    }
    return 0;
}

Compilation message (stderr)

friends.cpp: In function 'bool backtrack(std::vector<int>&, int, int, int, int)':
friends.cpp:23:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     while (it < ret.size()) {
            ~~~^~~~~~~~~~~~
friends.cpp:24:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         while (jt < edge[ret[it]].size()) {
                ~~~^~~~~~~~~~~~~~~~~~~~~~
friends.cpp: In function 'int main()':
friends.cpp:124:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         if (p + q <= edge[i].size()) fail();
             ~~~~~~^~~~~~~~~~~~~~~~~
friends.cpp:136:37: warning: format '%u' expects argument of type 'unsigned int', but argument 2 has type 'std::vector<int>::size_type {aka long unsigned int}' [-Wformat=]
         printf("%u", group[i].size());
                      ~~~~~~~~~~~~~~~^

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