Submission #133396

#	Time	Username	Problem	Language	Result	Execution time	Memory
133396		tlwpdus	Friends (BOI17_friends)	C++11	20 / 100	3 ms	1244 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];
vector<int> sel, cand;
void print() {
    printf("sel : ");
    for (int &v : sel) printf("%d ",v); printf("\n");
    printf("cand : ");
    for (int &v : cand) printf("%d ",v); printf("\n\n");
}
bool bt(int nq, int dep) {
    //printf("%d, %d\n",sel.size(),nq);
    //print();
    if (sel.size()<=p&&nq<=q) return true;
    if (dep>=p+q||cand.empty()) return false;
    int v = cand.back();
    cand.pop_back(); inc[v] = 0;
    chk[v] = 0;
    if (bt(nq,dep+1)) {
        chk[v] = -1;
        inc[v] = 0;
        return true;
    }
    sel.push_back(v);
    chk[v] = 1;
    for (int &there : lis[v]) {
        if (chk[there]==-1&&!inc[there]) {
            cand.push_back(there);
            inc[there] = 1;
        }
        nq -= (int)(chk[there]==1)*2-1;
    }
    if (bt(nq,dep+1)) {
        grp[gn].push_back(v);
        chk[v] = -1;
        inc[v] = 0;
        return true;
    }
    sel.pop_back();
    chk[v] = -1;
    cand.push_back(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) 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;
        sel.clear(); cand.clear(); sel.push_back(i);
        for (int &there : lis[i]) {
            cand.push_back(there);
            inc[there] = 1;
        }
        if (!bt(lis[i].size(),0)) pung();
        else {
            grp[gn].push_back(i);
            chk[i] = -1;
        }
        for (int &there : lis[i]) inc[there] = 0;
        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");
    }
    /*
    for (int i=0;i<gn;i++) {
        printf("%d : ",i);
        for (int &j : grp[i]) printf("%d ",j);
        printf("\n");
    }
    */

    return 0;
}

Compilation message (stderr)

friends.cpp: In function 'void print()':
friends.cpp:22:5: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
     for (int &v : sel) printf("%d ",v); printf("\n");
     ^~~
friends.cpp:22:41: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
     for (int &v : sel) printf("%d ",v); printf("\n");
                                         ^~~~~~
friends.cpp:24:5: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
     for (int &v : cand) printf("%d ",v); printf("\n\n");
     ^~~
friends.cpp:24:42: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
     for (int &v : cand) printf("%d ",v); printf("\n\n");
                                          ^~~~~~
friends.cpp: In function 'bool bt(int, int)':
friends.cpp:29:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     if (sel.size()<=p&&nq<=q) return true;
         ~~~~~~~~~~^~~
friends.cpp: In function 'void solve(int, int)':
friends.cpp:73: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:130: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:131:9: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
         for (int &v : grp[i]) printf("%d ",v); printf("\n");
         ^~~
friends.cpp:131: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:84: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:87:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d",&mi);
         ~~~~~^~~~~~~~~~
friends.cpp:91: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: 0 / 37
• Subtask 3: 0 / 12
• Subtask 4: 0 / 31