Submission #133545

#	Time	Username	Problem	Language	Result	Execution time	Memory
133545		tlwpdus	Friends (BOI17_friends)	C++11	100 / 100	762 ms	11256 KiB

friends

#include <bits/stdc++.h>

using namespace std;

typedef pair<int,int> pii;

int n, p, q;
vector<int> lis[3000];
int mat[3000][3000];

void pung() {
    puts("detention");
    exit(0);
}

int gn;
vector<int> grp[3000];
int chk[3000], inc[3000];
int sel[3000], cand[3000];
int sb, cb;
bool bt(int nq, int dep) {
    if (sb<=p&&nq<=q) return true;
    if (dep>=p+q||!cb||cb+sb>p+q) return false;
    int v = cand[--cb]; inc[v] = 0; chk[v] = 0;
    if (bt(nq,dep+1)) {
        chk[v] = -1;
        inc[v] = 0;
        return true;
    }
    sel[sb++] = v; chk[v] = 1;
    int psz = cb;
    for (int &there : lis[v]) {
        if (chk[there]==-1&&!inc[there]) {
            cand[cb++] = there; inc[there] = 1;
        }
        nq -= (int)(chk[there]==1)*2-1;
    }
    if (bt(nq,dep+1)) {
        grp[gn].push_back(v);
        chk[v] = -1;
        return true;
    }
    sb--; chk[v] = -1;
    while(cb>psz) inc[cand[--cb]] = 0;
    cand[cb++] = v;
    inc[v] = 1;
    return false;
}

void solve(int a, int b) {
    for (int &v : grp[a]) chk[v]++;
    for (int &v : grp[b]) chk[v]+=2;
    int c[2] = {0,0};
    for (int &v : grp[a]) {
        if (chk[v]!=3) continue;
        for (int &w : lis[v]) {
            if (chk[w]==3||chk[w]==0) continue;
            c[chk[w]-1]++;
        }
    }
    int t = (c[0]<c[1]?a:b);
    for (int i=0;i<grp[t].size();i++) {
        if (chk[grp[t][i]]!=3) continue;
        swap(grp[t][i],grp[t].back());
        grp[t].pop_back(); i--;
    }
    for (int &v : grp[a]) chk[v]=0;
    for (int &v : grp[b]) chk[v]=0;
}

set<pii> se;
int main() {
    scanf("%d%d%d",&n,&p,&q);
    for (int i=0;i<n;i++) {
        int mi;
        scanf("%d",&mi);
        if (mi>=p+q) pung();
        for (int j=0;j<mi;j++) {
            int a;
            scanf("%d",&a);
            mat[i][a] = 1;
            lis[i].push_back(a);
            if (a<=i) {
                if (se.find({a,i})==se.end()) pung();
                se.erase({a,i});
            }
            else se.insert({i,a});
        }
    }
    if (!se.empty()) pung();
    memset(chk,-1,sizeof(chk));
    for (int i=0;i<n;i++) {
        chk[i] = 1;
        for (int j=0;j<n;j++) inc[j] = 0;
        sb = cb = 0; sel[sb++] = i;
        for (int &there : lis[i]) {
            cand[cb++] = there;
            inc[there] = 1;
        }
        if (!bt(lis[i].size(),0)) pung();
        else {
            grp[gn].push_back(i);
            chk[i] = -1;
        }
        gn++;
    }
    memset(chk,0,sizeof(chk));
    for (int i=0;i<n;i++) {
        for (int j=i+1;j<n;j++) {
            solve(i,j);
        }
    }
    puts("home");
    int cnt = 0;
    for (int i=0;i<n;i++) cnt += (grp[i].size()>0);
    printf("%d\n",cnt);
    for (int i=0;i<n;i++) {
        if (grp[i].empty()) continue;
        printf("%d ",grp[i].size());
        for (int &v : grp[i]) printf("%d ",v); printf("\n");
    }

    return 0;
}

Compilation message (stderr)

friends.cpp: In function 'void solve(int, int)':
friends.cpp:62:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i=0;i<grp[t].size();i++) {
                  ~^~~~~~~~~~~~~~
friends.cpp: In function 'int main()':
friends.cpp:119:35: warning: format '%d' expects argument of type 'int', but argument 2 has type 'std::vector<int>::size_type {aka long unsigned int}' [-Wformat=]
         printf("%d ",grp[i].size());
                      ~~~~~~~~~~~~~^
friends.cpp:120:9: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
         for (int &v : grp[i]) printf("%d ",v); printf("\n");
         ^~~
friends.cpp:120:48: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
         for (int &v : grp[i]) printf("%d ",v); printf("\n");
                                                ^~~~~~
friends.cpp:73:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d%d%d",&n,&p,&q);
     ~~~~~^~~~~~~~~~~~~~~~~~~
friends.cpp:76:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d",&mi);
         ~~~~~^~~~~~~~~~
friends.cpp:80:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
             scanf("%d",&a);
             ~~~~~^~~~~~~~~

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