oj.uz

Submission #133407

# Submission time Handle Problem Language Result Execution time Memory
133407 2019-07-20T14:31:04 Z tlwpdus Friends (BOI17_friends) C++11
20 / 100
 6 ms 1272 KB 
#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, nop;
void print() {
    printf("sel : ");
    for (int &v : sel) printf("%d ",v); printf("\n");
    printf("nop : ");
    for (int &v : nop) 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; nop.push_back(v);
    if (bt(nq,dep+1)) {
        chk[v] = -1;
        inc[v] = 0;
        return true;
    }
    //for (int i=0;i<n;i++) printf("%2d ",chk[i]); printf("\n");
    //for (int i=0;i<n;i++) printf("%2d ",inc[i]); printf("\n");
    nop.pop_back();
    sel.push_back(v);
    chk[v] = 1;
    int psz = cand.size();
    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;
    while(cand.size()>psz) {
        inc[cand.back()] = 0;
        cand.pop_back();
    }
    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(); nop.clear(); sel.push_back(i);
        for (int &there : lis[i]) {
            cand.push_back(there);
            inc[there] = 1;
        }
        //printf("%d!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!\n",i);
        if (!bt(lis[i].size(),0)) pung();
        else {
            grp[gn].push_back(i);
            chk[i] = -1;
        }
        for (int &there : lis[i]) inc[there] = 0;
        //printf("%d : ",i);
        //for (int &j : grp[i]) printf("%d ",j);
        //printf("\n");
        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

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 : nop) printf("%d ",v); printf("\n");
     ^~~
friends.cpp:24:41: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
     for (int &v : nop) printf("%d ",v); printf("\n");
                                         ^~~~~~
friends.cpp:26:5: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
     for (int &v : cand) printf("%d ",v); printf("\n\n");
     ^~~
friends.cpp:26: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:33:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     if (sel.size()<=p&&nq<=q) return true;
         ~~~~~~~~~~^~~
friends.cpp:64:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     while(cand.size()>psz) {
           ~~~~~~~~~~~^~~~
friends.cpp: In function 'void solve(int, int)':
friends.cpp:85: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:146: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:147:9: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
         for (int &v : grp[i]) printf("%d ",v); printf("\n");
         ^~~
friends.cpp:147: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:96: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:99:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d",&mi);
         ~~~~~^~~~~~~~~~
friends.cpp:103:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
             scanf("%d",&a);
             ~~~~~^~~~~~~~~

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 508 KB Output is correct
2 Correct 2 ms 504 KB Output is correct
3 Correct 2 ms 504 KB Output is correct
4 Correct 2 ms 504 KB Output is correct
5 Correct 2 ms 504 KB Output is correct
6 Correct 3 ms 504 KB Output is correct
7 Correct 2 ms 504 KB Output is correct
8 Correct 2 ms 504 KB Output is correct

Subtask #2
0 / 37.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 504 KB Output is correct
2 Incorrect 6 ms 1272 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 504 KB Output is correct
2 Incorrect 6 ms 1272 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 508 KB Output is correct
2 Correct 2 ms 504 KB Output is correct
3 Correct 2 ms 504 KB Output is correct
4 Correct 2 ms 504 KB Output is correct
5 Correct 2 ms 504 KB Output is correct
6 Correct 3 ms 504 KB Output is correct
7 Correct 2 ms 504 KB Output is correct
8 Correct 2 ms 504 KB Output is correct
9 Correct 2 ms 504 KB Output is correct
10 Incorrect 6 ms 1272 KB Output isn't correct
11 Halted 0 ms 0 KB -