QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#53578#34. Friendsnot_so_organic100 ✓8ms4132kbC++118.3kb2022-10-05 13:35:042022-10-05 13:35:05

Judging History

你现在查看的是最新测评结果

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2022-10-05 13:35:05]
  • 评测
  • 测评结果:100
  • 用时:8ms
  • 内存:4132kb
  • [2022-10-05 13:35:04]
  • 提交

answer

#include <stdio.h>
#include <vector>
#include <iostream>
#include <stack>
#include <set>
#include <cstdlib>

using namespace std;

int n, p, q;
vector<vector<int>> G;

vector<bool> visited; // already put in some previous group
vector<bool> in; // active group
vector<bool> undecided; // neighbors of active group, may go into active group.
stack<int> undecidedStack; // a stack of the yet undecided neighbors of the active group
vector<bool> out; // neighbors of active group, may NOT go into active group.

vector<set<int>> output;
vector<int> myGroup;


bool branchWithFirstVertexOut(int groupSize, int neighSize);
bool mainBranch(int groupSize, int neighSize);
bool branchWithFirstVertexInGroup(int groupSize, int neighSize);
bool findgroup(int v);

void fix(int i, int j);
int firstConflict();
bool isValidGroup(const set<int> &s);


void printSet(const set<int> &S);
void printPartition();


// ----------------------------------------
// ---------------------------------------------- MAIN GREEDY
// ----------------------------------------

int main() {

    scanf("%d %d %d", &n, &p, &q);
    G = vector<vector<int>> ();
    bool success = true;

    // read graph
    for (int i = 0; i < n && success; ++i) {
        int mi;
        scanf("%d", &mi);

        if (mi > p + q)
            success = false;

        G.push_back(vector<int> (mi, 0));

        for (int j = 0; j < mi; ++j) {
            scanf("%d", &(G[i][j]));
        }
    }

    // verify undirected
    for (int u = 0; u < n && success; ++u) {
        for (int i = 0; i < G[u].size(); ++i) {
            int v = G[u][i];
            bool foundu = false;

            for (int j = 0; j < G[v].size(); ++j) {
                foundu |= (G[v][j] == u);
            }

            success &= foundu;
        }
    }

    // check that each vertex can be put in some group.
    visited = vector<bool> (n, false);
    in = vector<bool> (n, false);
    undecided = vector<bool> (n, false);
    out = vector<bool> (n, false);

    myGroup = vector<int>(n, -1);

    for (int i = 0; i < n && success; ++i) {
        //cout << i << endl;
        if (visited[i])
            continue;

        if (!findgroup(i)) {
            success = false;
            break;
        }

        // resolve conflicts between new group and old groups
        int p = output.size() - 1;

        //printf("set:\n");
        //printSet(output[p]);

        while (true) {
            int conf = firstConflict();

            //printf("CONF %d\n", conf);
            if (conf == -1)
                break;

            fix(p, conf);
        }

        for (set<int>::iterator it = output[p].begin(); it != output[p].end(); ++it) {
            myGroup[*it] = p;
        }

        //printf("second\n");
        //printPartition();

    }

    if (success) {
        printf("home\n");
        printPartition();
    } else {
        printf("detention\n");
    }

    return 0;

}

// ----------------------------
// ---------------------- HELPER FUCNTIONS FOR BRANCHING ALGORITHM BELOW
// ----------------------------

inline int popUndecided() {
    int v = undecidedStack.top();
    undecidedStack.pop();
    undecided[v] = false;
    return v;
}

inline void pushUndecided(int v) {
    undecided[v] = true;
    undecidedStack.push(v);
}

vector<int> freshNeighbors(int v) {
    vector<int> ans;

    for (int i = 0; i < G[v].size(); ++i) {
        if (!(in[G[v][i]] || undecided[G[v][i]] || out[G[v][i]]))
            ans.push_back(G[v][i]);
    }

    return ans;
}

// ------------------------------------------------- BRANCHING
// ------------------------------------------------- FINDING IF V CAN BE PUT IN A GROUP
bool findgroup(int v) {
    pushUndecided(v);
    bool ans = branchWithFirstVertexInGroup(0, 0);
    popUndecided();

    if (ans)
        output[output.size() - 1].insert(v);

    visited[v] = true;
    return ans;
}

// groupsize is the current size of the group, cutsize is the size of the cut
bool mainBranch(int groupSize, int cutSize) {

    if (groupSize > p || cutSize > q || groupSize + cutSize + undecidedStack.size() > p + q)
        return false;

    if (undecidedStack.empty()) {
        output.push_back(set<int>());
        return true;
    }

    return (branchWithFirstVertexOut(groupSize, cutSize) || branchWithFirstVertexInGroup(groupSize, cutSize));

}

bool branchWithFirstVertexOut(int groupSize, int cutSize) {
    int v = popUndecided();
    out[v] = true;

    for (int i = 0; i < G[v].size(); ++i) {
        cutSize += in[G[v][i]];
    }

    bool ans = mainBranch(groupSize, cutSize);

    out[v] = false;
    pushUndecided(v);

    return ans;
}

bool branchWithFirstVertexInGroup(int groupSize, int cutSize) {
    int v = popUndecided();
    in[v] = true;

    vector<int> nv = freshNeighbors(v);

    for (int i = 0; i < nv.size(); ++i) {
        pushUndecided(nv[i]);
    }

    for (int i = 0; i < G[v].size(); ++i) {
        cutSize += out[G[v][i]];
    }

    bool ans = mainBranch(groupSize + 1, cutSize);

    if (ans) {
        output[output.size() - 1].insert(v);
    }

    in[v] = false;

    for (int i = 0; i < nv.size(); ++i) {
        popUndecided();
    }

    pushUndecided(v);

    if (ans)
        visited[v] = true; // If found a group with v in it, v becomes visited.

    return ans;
}

int firstConflict() {
    int p = output.size() - 1;

    if (p < 0)
        return - 1;

    for (set<int>::iterator s = output[p].begin(); s != output[p].end(); ++s) {
        if (*s < 0 || *s > n - 1) {
            cout << "wtf" << endl;
            exit(0);
        }

        if (myGroup[*s] != -1 && myGroup[*s] != p)
            return myGroup[*s];
    }

    return -1;
}

// i is the new group, j is the old one.
void fix(int i, int j) {
    set<int> si(output[i]), sj(output[j]), nsi(output[i]), nsj(output[j]);

    for (set<int>::iterator it = si.begin(); it != si.end(); ++it) {
        if (sj.count(*it) != 0) {
            nsi.erase(*it);
            nsj.erase(*it);
        }
    }

    /*
    printf("si:\n");
    printSet(si);
    printf("nsi:\n");
    printSet(nsi);
    printf("sj:\n");
    printSet(sj);
    printf("nsj:\n");
    printSet(nsj);
    */
    /*
    if(nsj.empty() && isValidGroup(si)) {
        // cout << "i should be here" << endl;
        // kill the conflict group, update myGroup.
        for(set<int>::iterator it = sj.begin(); it != sj.end(); ++it) {myGroup[*it] = i;}
        output[j] = set<int>();
    } else
    */
    if (isValidGroup(nsi)) {
        // make last group smaller
        printf("nsi was valid\n");
        output[i] = set<int> (nsi);
    } else if (isValidGroup(nsj)) {
        // make the conflict group smaller, update myGroup.
        for (set<int>::iterator it = sj.begin(); it != sj.end(); ++it) {
            if (nsj.count(*it) == 0)
                myGroup[*it] = i;
        }

        output[j] = set<int> (nsj);
    } else {
        printf("goddammit\n");
        exit(1);
    }
}

bool isValidGroup(const set<int> &s) {
    //printf("is valid group:\n");
    //printSet(s);

    int cnt = 0;

    if (s.empty())
        return true;

    for (set<int>::iterator itr = s.begin(); itr != s.end(); ++itr) {
        int u = *itr;

        //printf("vertex u: %d\n", u);
        for (int i = 0; i < G[u].size(); ++i) {
            int v = G[u][i];
            cnt += (s.count(G[u][i]) == 0 ? 1 : 0);
            //printf("vertex v: %d   count: %d\n", v, cnt);
        }
    }

    //printf("answer is %d\n", (cnt <= q ? 1 : 0));
    return cnt <= q;
}


void printSet(const set<int> &S) {
    if (S.empty())
        return;

    printf("%d", S.size());

    for (set<int>::iterator s = S.begin(); s != S.end(); ++s) {
        printf(" %d", (*s));
    }

    printf("\n");
}

void printPartition() {
    // DEBUG:
    //printf("current partition\n");
    // ---
    int numGroups = 0;

    for (int i = 0; i < output.size(); ++i) {
        if (!output[i].empty())
            numGroups++;
    }

    printf("%d\n", numGroups);

    for (int i = 0; i < output.size(); ++i) {
        //cout << "-- " << i << "--  " << endl;
        printSet(output[i]);
    }
}

詳細信息

Subtask #1:

score: 20
Accepted

Test #1:

score: 20
Accepted
time: 1ms
memory: 3844kb

input:

2 2 2
1 1
0

output:

detention

result:

ok no solution

Test #2:

score: 0
Accepted
time: 2ms
memory: 3820kb

input:

5 1 2
2 1 4
2 0 2
2 1 4
0
2 0 2

output:

home
5
1 0
1 1
1 2
1 3
1 4

result:

ok correct plan!

Test #3:

score: 0
Accepted
time: 2ms
memory: 3736kb

input:

10 2 2
2 1 5
2 0 2
2 1 3
2 2 4
1 3
1 0
1 7
1 6
1 9
1 8

output:

home
10
1 0
1 1
1 2
1 3
1 4
1 5
1 6
1 7
1 8
1 9

result:

ok correct plan!

Test #4:

score: 0
Accepted
time: 0ms
memory: 3692kb

input:

15 2 3
3 1 2 3
2 0 2
3 0 1 3
3 0 2 4
4 3 5 6 8
1 4
2 4 7
3 6 8 9
3 4 7 9
2 7 8
2 11 13
3 10 12 13
2 11 13
3 10 11 12
0

output:

home
14
1 0
1 1
1 2
1 3
2 4 5
1 6
1 7
1 8
1 9
1 10
1 11
1 12
1 13
1 14

result:

ok correct plan!

Test #5:

score: 0
Accepted
time: 1ms
memory: 3812kb

input:

16 3 3
2 1 2
3 0 2 7
4 0 1 6 9
2 4 14
3 3 12 13
2 6 7
3 2 5 7
3 1 5 6
0
2 2 14
2 11 12
2 10 12
3 4 10 11
3 4 14 15
4 3 9 13 15
2 13 14

output:

home
12
3 0 1 2
1 3
1 4
1 5
1 6
1 7
1 8
1 9
1 10
1 11
1 12
3 13 14 15

result:

ok correct plan!

Test #6:

score: 0
Accepted
time: 2ms
memory: 3740kb

input:

16 4 4
3 1 2 3
3 0 2 3
6 0 1 3 5 6 9
4 0 1 2 11
4 5 6 7 15
5 2 4 6 7 15
4 2 4 5 7
3 4 5 6
3 9 10 11
5 2 8 10 11 14
5 8 9 11 12 13
4 3 8 9 10
4 10 13 14 15
4 10 12 14 15
4 9 12 13 15
5 4 5 12 13 14

output:

detention

result:

ok no solution

Test #7:

score: 0
Accepted
time: 2ms
memory: 3744kb

input:

16 3 3
3 1 3 6
3 0 2 3
2 1 3
4 0 1 2 12
2 5 6
4 4 6 13 14
4 0 4 5 13
3 8 9 15
2 7 9
2 7 8
2 11 12
2 10 12
3 3 10 11
4 5 6 14 15
3 5 13 15
3 7 13 14

output:

detention

result:

ok no solution

Test #8:

score: 0
Accepted
time: 2ms
memory: 3696kb

input:

16 5 5
3 1 2 4
1 0
2 0 3
4 2 4 5 13
3 0 1 3
5 3 6 7 8 9
3 5 7 9
6 5 6 8 9 12 14
4 5 7 9 14
4 5 6 7 8
4 11 12 13 14
4 10 12 13 14
5 7 10 11 13 14
4 3 10 11 12
5 7 8 10 11 12
0

output:

detention

result:

ok no solution

Subtask #2:

score: 37
Accepted

Test #9:

score: 37
Accepted
time: 2ms
memory: 3752kb

input:

2 2 2
1 1
0

output:

detention

result:

ok no solution

Test #10:

score: 0
Accepted
time: 2ms
memory: 3704kb

input:

200 8 2
5 1 4 5 6 7
6 0 2 3 5 6 10
5 1 3 5 6 7
5 1 2 4 6 7
3 0 3 6
4 0 1 2 6
7 0 1 2 3 4 5 7
5 0 2 3 6 10
6 9 10 11 12 13 14
7 8 10 11 12 13 14 15
8 1 7 8 9 11 12 13 14
7 8 9 10 12 13 14 15
4 8 9 10 11
5 8 9 10 11 15
5 8 9 10 11 15
4 9 11 13 14
8 17 18 19 20 21 22 23 35
7 16 18 19 20 21 22 23
6 16 1...

output:

home
26
8 0 1 2 3 4 5 6 7
8 8 9 10 11 12 13 14 15
8 16 17 18 19 20 21 22 23
8 24 25 26 27 28 29 30 31
8 32 33 34 35 36 37 38 39
8 40 41 42 43 44 45 46 47
8 48 49 50 51 52 53 54 55
7 56 57 58 59 60 61 62
8 63 64 65 66 67 68 69 70
8 71 72 73 74 75 76 77 78
8 79 80 81 82 83 84 85 86
8 87 88 89 90 91 92...

result:

ok correct plan!

Test #11:

score: 0
Accepted
time: 3ms
memory: 3756kb

input:

150 5 2
2 1 2
4 0 2 3 6
2 0 1
5 1 4 5 6 7
4 3 5 6 7
4 3 4 6 7
5 1 3 4 5 7
4 3 4 5 6
4 9 10 12 17
5 8 10 11 12 13
3 8 9 12
2 9 12
4 8 9 10 11
4 9 14 15 16
4 13 15 16 17
4 13 14 16 17
4 13 14 15 17
4 8 14 15 16
4 19 20 21 22
5 18 20 21 22 46
4 18 19 21 22
5 18 19 20 22 31
4 18 19 20 21
4 24 25 26 27
3...

output:

home
37
3 0 1 2
5 3 4 5 6 7
5 8 9 10 11 12
5 13 14 15 16 17
5 18 19 20 21 22
5 23 24 25 26 27
1 28
2 29 30
5 31 32 33 34 35
5 36 37 38 39 40
4 41 42 43 44
5 45 46 47 48 49
5 50 51 52 53 54
3 55 56 57
5 58 59 60 61 62
1 63
1 64
5 65 66 67 68 69
5 70 71 72 73 74
5 75 76 77 78 79
5 80 81 82 83 84
4 85 ...

result:

ok correct plan!

Test #12:

score: 0
Accepted
time: 0ms
memory: 3860kb

input:

250 6 2
5 1 2 3 4 5
3 0 3 4
5 0 3 4 5 17
4 0 1 2 5
4 0 1 2 5
5 0 2 3 4 12
4 7 9 10 11
6 6 8 9 10 11 46
4 7 9 10 11
6 6 7 8 10 11 43
5 6 7 8 9 11
5 6 7 8 9 10
6 5 13 14 15 16 17
5 12 14 15 16 17
4 12 13 15 16
4 12 13 14 17
4 12 13 14 17
5 2 12 13 15 16
5 19 20 21 22 23
5 18 20 21 22 23
5 18 19 21 22 ...

output:

detention

result:

ok no solution

Test #13:

score: 0
Accepted
time: 2ms
memory: 3832kb

input:

250 7 2
6 1 2 3 4 5 6
6 0 2 3 4 5 6
7 0 1 3 4 5 6 7
6 0 1 2 4 5 6
6 0 1 2 3 5 6
6 0 1 2 3 4 6
7 0 1 2 3 4 5 8
2 2 8
2 6 7
4 10 11 12 17
3 9 11 12
4 9 10 12 19
3 9 10 11
5 14 15 17 18 19
6 13 15 16 17 18 19
6 13 14 16 17 18 19
5 14 15 17 18 19
7 9 13 14 15 16 18 19
6 13 14 15 16 17 19
7 11 13 14 15 1...

output:

detention

result:

ok no solution

Test #14:

score: 0
Accepted
time: 2ms
memory: 3844kb

input:

250 5 2
3 1 3 7
3 0 2 3
3 1 3 4
3 0 1 2
1 2
3 6 7 8
5 1 5 7 8 9
4 0 5 6 8
4 5 6 7 9
2 6 8
2 14 25
3 12 13 14
2 11 14
2 11 44
3 10 11 12
5 16 17 18 19 20
3 15 18 19
3 15 18 19
4 15 16 17 28
3 15 16 17
5 15 21 22 23 24
4 20 22 23 24
5 20 21 23 24 36
4 20 21 22 24
4 20 21 22 23
5 10 26 27 28 29
4 25 27...

output:

detention

result:

ok no solution

Test #15:

score: 0
Accepted
time: 0ms
memory: 3856kb

input:

100 5 0
4 1 2 3 4
4 0 2 3 4
3 0 1 4
3 0 1 4
4 0 1 2 3
3 6 7 8
4 5 7 8 9
4 5 6 8 9
4 5 6 7 9
3 6 7 8
3 11 12 14
3 10 12 14
4 10 11 13 14
2 12 14
4 10 11 12 13
2 16 17
2 15 17
2 15 16
4 19 20 21 22
4 18 20 21 22
3 18 19 21
4 18 19 20 22
3 18 19 21
4 24 25 26 27
3 23 26 27
3 23 26 27
4 23 24 25 27
4 23...

output:

home
24
5 0 1 2 3 4
5 5 6 7 8 9
5 10 11 12 13 14
3 15 16 17
5 18 19 20 21 22
5 23 24 25 26 27
5 28 29 30 31 32
5 33 34 35 36 37
5 38 39 40 41 42
5 43 44 45 46 47
5 48 49 50 51 52
5 53 54 55 56 57
5 58 59 60 61 62
4 63 64 65 66
2 67 68
2 69 70
5 71 72 73 74 75
5 76 77 78 79 80
5 81 82 83 84 85
5 86 8...

result:

ok correct plan!

Test #16:

score: 0
Accepted
time: 1ms
memory: 3892kb

input:

250 10 1
9 1 2 3 4 5 6 7 8 9
9 0 2 3 4 5 6 7 8 9
9 0 1 3 4 5 6 7 8 9
9 0 1 2 4 5 6 7 8 9
9 0 1 2 3 5 6 7 8 9
9 0 1 2 3 4 6 7 8 9
9 0 1 2 3 4 5 7 8 9
9 0 1 2 3 4 5 6 8 9
9 0 1 2 3 4 5 6 7 9
10 0 1 2 3 4 5 6 7 8 12
9 11 12 13 14 15 16 17 18 19
9 10 12 13 14 15 16 17 18 19
10 9 10 11 13 14 15 16 17 18 ...

output:

home
28
10 0 1 2 3 4 5 6 7 8 9
10 10 11 12 13 14 15 16 17 18 19
10 20 21 22 23 24 25 26 27 28 29
10 30 31 32 33 34 35 36 37 38 39
9 40 41 42 43 44 45 46 47 48
10 49 50 51 52 53 54 55 56 57 58
10 59 60 61 62 63 64 65 66 67 68
10 69 70 71 72 73 74 75 76 77 78
10 79 80 81 82 83 84 85 86 87 88
10 89 90 ...

result:

ok correct plan!

Subtask #3:

score: 12
Accepted

Dependency #2:

100%
Accepted

Test #17:

score: 12
Accepted
time: 2ms
memory: 3832kb

input:

2 2 2
1 1
0

output:

detention

result:

ok no solution

Test #18:

score: 0
Accepted
time: 3ms
memory: 3888kb

input:

1000 10 0
6 1 2 3 5 6 7
7 0 2 3 4 5 6 7
7 0 1 3 4 5 6 7
7 0 1 2 4 5 6 7
6 1 2 3 5 6 7
7 0 1 2 3 4 6 7
7 0 1 2 3 4 5 7
7 0 1 2 3 4 5 6
9 9 10 11 12 13 14 15 16 17
8 8 10 12 13 14 15 16 17
8 8 9 11 12 13 14 15 17
8 8 10 12 13 14 15 16 17
9 8 9 10 11 13 14 15 16 17
8 8 9 10 11 12 15 16 17
7 8 9 10 11 1...

output:

home
111
8 0 1 2 3 4 5 6 7
10 8 9 10 11 12 13 14 15 16 17
10 18 19 20 21 22 23 24 25 26 27
10 28 29 30 31 32 33 34 35 36 37
10 38 39 40 41 42 43 44 45 46 47
10 48 49 50 51 52 53 54 55 56 57
4 58 59 60 61
9 62 63 64 65 66 67 68 69 70
2 71 72
10 73 74 75 76 77 78 79 80 81 82
10 83 84 85 86 87 88 89 90...

result:

ok correct plan!

Test #19:

score: 0
Accepted
time: 1ms
memory: 3980kb

input:

1250 8 1
7 1 2 3 4 5 6 7
7 0 2 3 4 5 6 7
7 0 1 3 4 5 6 7
7 0 1 2 4 5 6 7
8 0 1 2 3 5 6 7 23
7 0 1 2 3 4 6 7
7 0 1 2 3 4 5 7
7 0 1 2 3 4 5 6
7 9 10 11 12 13 14 15
7 8 10 11 12 13 14 15
7 8 9 11 12 13 14 15
8 8 9 10 12 13 14 15 51
7 8 9 10 11 13 14 15
7 8 9 10 11 12 14 15
7 8 9 10 11 12 13 15
7 8 9 10...

output:

home
178
8 0 1 2 3 4 5 6 7
8 8 9 10 11 12 13 14 15
8 16 17 18 19 20 21 22 23
8 24 25 26 27 28 29 30 31
8 32 33 34 35 36 37 38 39
8 40 41 42 43 44 45 46 47
8 48 49 50 51 52 53 54 55
8 56 57 58 59 60 61 62 63
1 64
8 65 66 67 68 69 70 71 72
8 73 74 75 76 77 78 79 80
8 81 82 83 84 85 86 87 88
8 89 90 91...

result:

ok correct plan!

Test #20:

score: 0
Accepted
time: 1ms
memory: 3960kb

input:

1200 9 2
7 1 2 3 4 5 7 8
7 0 3 4 5 6 7 8
8 0 3 4 5 6 7 8 29
6 0 1 2 4 7 8
8 0 1 2 3 5 6 7 8
6 0 1 2 4 7 8
3 1 2 4
8 0 1 2 3 4 5 8 10
7 0 1 2 3 4 5 7
8 10 11 12 13 14 15 16 17
9 7 9 11 12 13 14 15 16 17
8 9 10 12 13 14 15 16 17
7 9 10 11 13 16 17 27
8 9 10 11 12 14 15 16 17
7 9 10 11 13 15 16 17
7 9 ...

output:

home
161
9 0 1 2 3 4 5 6 7 8
9 9 10 11 12 13 14 15 16 17
8 18 19 20 21 22 23 24 25
9 26 27 28 29 30 31 32 33 34
1 35
7 36 37 38 39 40 41 42
9 43 44 45 46 47 48 49 50 51
9 52 53 54 55 56 57 58 59 60
9 61 62 63 64 65 66 67 68 69
9 70 71 72 73 74 75 76 77 78
9 79 80 81 82 83 84 85 86 87
9 88 89 90 91 9...

result:

ok correct plan!

Test #21:

score: 0
Accepted
time: 1ms
memory: 3920kb

input:

1250 9 2
6 1 3 4 5 6 8
7 0 2 3 4 5 6 20
4 1 3 5 6
6 0 1 2 4 5 6
5 0 1 3 5 6
6 0 1 2 3 4 6
6 0 1 2 3 4 5
7 8 9 10 12 13 14 15
8 0 7 9 10 11 12 14 15
8 7 8 10 11 12 13 14 15
8 7 8 9 11 12 13 14 15
6 8 9 10 12 14 15
8 7 8 9 10 11 14 15 38
5 7 9 10 14 15
8 7 8 9 10 11 12 13 15
8 7 8 9 10 11 12 13 14
7 1...

output:

home
165
7 0 1 2 3 4 5 6
9 7 8 9 10 11 12 13 14 15
9 16 17 18 19 20 21 22 23 24
9 25 26 27 28 29 30 31 32 33
9 34 35 36 37 38 39 40 41 42
9 43 44 45 46 47 48 49 50 51
7 52 53 54 55 56 57 58
9 59 60 61 62 63 64 65 66 67
9 68 69 70 71 72 73 74 75 76
9 77 78 79 80 81 82 83 84 85
9 86 87 88 89 90 91 92 ...

result:

ok correct plan!

Test #22:

score: 0
Accepted
time: 3ms
memory: 3864kb

input:

1800 6 2
5 1 2 3 4 5
6 0 2 3 4 5 14
5 0 1 3 4 5
5 0 1 2 4 5
6 0 1 2 3 5 26
6 0 1 2 3 4 307
6 7 8 9 10 11 12
5 6 8 9 10 11
4 6 7 9 11
4 6 7 8 10
5 6 7 9 11 13
4 6 7 8 10
2 6 13
2 10 12
5 1 15 16 17 35
3 14 16 17
3 14 15 17
3 14 15 16
4 19 20 21 22
4 18 20 21 22
4 18 19 21 22
6 18 19 20 22 32 40
4 18 ...

output:

detention

result:

ok no solution

Test #23:

score: 0
Accepted
time: 4ms
memory: 3960kb

input:

1800 7 2
6 1 2 3 4 5 6
9 0 2 3 4 5 6 13 19 484
6 0 1 3 4 5 6
6 0 1 2 4 5 6
6 0 1 2 3 5 6
6 0 1 2 3 4 6
6 0 1 2 3 4 5
6 8 9 10 11 12 13
6 7 9 10 12 13 24
4 7 8 10 13
5 7 8 9 11 13
3 7 10 12
3 7 8 11
5 1 7 8 9 10
5 15 16 17 18 19
6 14 16 17 18 19 20
5 14 15 17 18 19
4 14 15 16 18
6 14 15 16 17 19 20
5...

output:

detention

result:

ok no solution

Test #24:

score: 0
Accepted
time: 3ms
memory: 3876kb

input:

2000 5 2
3 2 3 4
2 2 3
4 0 1 3 4
5 0 1 2 4 9
5 0 1 2 3 10
2 6 9
4 5 7 8 9
3 6 8 9
3 6 7 9
6 3 5 6 7 8 11
5 4 11 12 13 14
5 9 10 12 13 14
3 10 11 13
4 10 11 12 14
3 10 11 13
4 16 17 18 19
5 15 17 18 19 34
5 15 16 18 19 24
4 15 16 17 19
4 15 16 17 18
4 21 22 23 24
5 20 22 23 24 33
4 20 21 23 24
4 20 2...

output:

detention

result:

ok no solution

Subtask #4:

score: 31
Accepted

Test #25:

score: 31
Accepted
time: 3ms
memory: 3692kb

input:

2 2 2
1 1
0

output:

detention

result:

ok no solution

Test #26:

score: 0
Accepted
time: 6ms
memory: 4060kb

input:

1900 6 5
5 2 3 4 5 6
4 2 4 5 7
5 0 1 3 4 5
6 0 2 4 5 6 11
5 0 1 2 3 6
4 0 1 2 3
8 0 3 4 7 8 9 10 11
5 1 6 8 9 11
5 6 7 9 10 11
4 6 7 8 11
3 6 8 11
6 3 6 7 8 9 10
5 13 15 16 17 29
6 12 14 15 16 17 37
4 13 15 16 17
5 12 13 14 16 17
6 12 13 14 15 17 37
7 12 13 14 15 16 24 32
5 19 20 21 22 28
6 18 20 21...

output:

home
601
6 0 1 2 3 4 5
6 6 7 8 9 10 11
6 12 13 14 15 16 17
6 18 19 20 21 22 23
6 24 25 26 27 28 29
6 30 31 32 33 34 35
6 36 37 38 39 40 41
5 42 43 44 45 46
1 47
1 48
1 49
1 50
1 51
1 52
1 53
6 54 55 56 57 58 59
1 60
1 61
6 62 63 64 65 66 67
6 68 69 70 71 72 73
6 74 75 76 77 78 79
1 80
1 81
1 82
1 83...

result:

ok correct plan!

Test #27:

score: 0
Accepted
time: 0ms
memory: 4132kb

input:

1800 5 5
4 1 2 6 10
5 0 2 4 9 13
2 0 1
3 4 5 23
4 1 3 7 25
5 3 6 7 8 9
5 0 5 7 8 9
6 4 5 6 8 9 14
4 5 6 7 9
5 1 5 6 7 8
5 0 11 12 13 14
4 10 12 13 14
4 10 11 13 14
7 1 10 11 12 14 17 31
5 7 10 11 12 13
6 16 19 21 24 29 33
1 15
5 13 18 19 20 21
6 17 19 20 21 24 26
5 15 17 18 20 21
4 17 18 19 21
5 15 ...

output:

home
565
1 0
1 1
1 2
1 3
1 4
5 5 6 7 8 9
5 10 11 12 13 14
2 15 16
5 17 18 19 20 21
5 22 23 24 25 26
5 27 28 29 30 31
5 32 33 34 35 36
5 37 38 39 40 41
1 42
1 43
5 44 45 46 47 48
5 49 50 51 52 53
5 54 55 56 57 58
5 59 60 61 62 63
5 64 65 66 67 68
5 69 70 71 72 73
1 74
1 75
1 76
1 77
1 78
5 79 80 81 8...

result:

ok correct plan!

Test #28:

score: 0
Accepted
time: 8ms
memory: 4028kb

input:

1650 6 5
5 1 3 4 5 7
6 0 2 3 4 5 25
4 1 3 4 5
7 0 1 2 4 5 12 28
6 0 1 2 3 5 13
5 0 1 2 3 4
4 7 8 10 11
6 0 6 8 9 10 11
6 6 7 9 10 11 53
4 7 8 10 11
7 6 7 8 9 11 34 52
6 6 7 8 9 10 55
4 3 13 20 22
3 4 12 14
6 13 15 16 17 18 19
7 14 16 17 18 19 26 36
5 14 15 17 18 19
7 14 15 16 18 19 34 46
5 14 15 16 ...

output:

home
405
6 0 1 2 3 4 5
6 6 7 8 9 10 11
1 12
1 13
6 14 15 16 17 18 19
6 20 21 22 23 24 25
6 26 27 28 29 30 31
6 32 33 34 35 36 37
1 38
6 39 40 41 42 43 44
6 45 46 47 48 49 50
6 51 52 53 54 55 56
6 57 58 59 60 61 62
6 63 64 65 66 67 68
6 69 70 71 72 73 74
6 75 76 77 78 79 80
6 81 82 83 84 85 86
1 87
1...

result:

ok correct plan!

Test #29:

score: 0
Accepted
time: 0ms
memory: 3712kb

input:

1050 10 5
3 1 9 10
5 0 3 8 22 270
6 4 5 7 9 10 11
7 1 4 5 6 9 10 11
9 2 3 5 6 7 8 9 10 11
7 2 3 4 6 9 10 11
7 3 4 5 7 8 9 10
7 2 4 6 8 9 10 11
6 1 4 6 7 10 11
9 0 2 3 4 5 6 7 10 11
9 0 2 3 4 5 6 7 8 9
8 2 3 4 5 7 8 9 22
9 13 14 15 16 17 18 19 20 21
10 12 14 15 16 17 18 19 20 21 37
10 12 13 15 16 18 ...

output:

detention

result:

ok no solution

Test #30:

score: 0
Accepted
time: 6ms
memory: 3972kb

input:

1300 7 7
7 2 3 4 5 6 9 32
5 2 3 4 5 6
8 0 1 3 4 5 6 9 12
7 0 1 2 4 5 10 11
6 0 1 2 3 5 6
6 0 1 2 3 4 6
6 0 1 2 4 5 9
5 8 9 11 12 13
5 7 9 10 11 13
9 0 2 6 7 8 10 11 12 13
6 3 8 9 11 12 13
8 3 7 8 9 10 12 13 31
6 2 7 9 10 11 13
6 7 8 9 10 11 12
8 15 16 17 18 19 20 24 32
6 14 16 17 18 19 20
7 14 15 17...

output:

detention

result:

ok no solution

Test #31:

score: 0
Accepted
time: 1ms
memory: 3844kb

input:

1300 9 4
5 2 3 4 6 7
6 3 4 5 6 7 13
7 0 3 4 5 6 7 8
6 0 1 2 4 5 8
8 0 1 2 3 5 6 7 8
8 1 2 3 4 6 7 8 16
8 0 1 2 4 5 7 8 14
8 0 1 2 4 5 6 8 12
6 2 3 4 5 6 7
7 10 11 12 13 14 15 16
6 9 12 13 14 15 16
7 9 12 13 14 15 16 17
9 7 9 10 11 13 14 15 16 17
9 1 9 10 11 12 14 15 16 17
9 6 9 10 11 12 13 15 16 17
...

output:

detention

result:

ok no solution

Test #32:

score: 0
Accepted
time: 3ms
memory: 3868kb

input:

2000 5 5
5 1 2 3 4 8
4 0 2 3 4
4 0 1 3 4
7 0 1 2 4 10 12 16
4 0 1 2 3
4 6 7 8 9
5 5 8 9 17 29
3 5 8 9
6 0 5 6 7 9 14
5 5 6 7 8 19
5 3 11 12 13 15
3 10 13 18
3 3 10 13
4 1 10 11 12
5 8 15 16 17 18
5 10 14 16 17 18
5 3 14 15 17 18
5 6 14 15 16 18
5 11 14 15 16 17
6 9 20 21 22 23 24
4 19 21 22 23
5 19 ...

output:

detention

result:

ok no solution

Test #33:

score: 0
Accepted
time: 8ms
memory: 4080kb

input:

2500 9 6
6 1 2 3 4 6 7
5 0 2 3 6 7
6 0 1 4 5 6 7
7 0 1 4 7 8 31 35
6 0 2 3 5 6 8
5 2 4 6 7 8
6 0 1 2 4 5 7
8 0 1 2 3 5 6 15 36
5 3 4 5 19 39
7 10 11 13 14 15 16 39
8 9 11 12 13 14 15 16 40
7 9 10 12 13 14 15 16
9 10 11 13 14 15 16 17 22 33
7 9 10 11 12 14 15 17
8 9 10 11 12 13 15 16 17
9 7 9 10 11 1...

output:

home
420
9 0 1 2 3 4 5 6 7 8
9 9 10 11 12 13 14 15 16 17
9 18 19 20 21 22 23 24 25 26
9 27 28 29 30 31 32 33 34 35
6 36 37 38 39 40 41
9 42 43 44 45 46 47 48 49 50
1 51
1 52
1 53
9 54 55 56 57 58 59 60 61 62
1 63
1 64
1 65
1 66
9 67 68 69 70 71 72 73 74 75
9 76 77 78 79 80 81 82 83 84
9 85 86 87 88 ...

result:

ok correct plan!

Test #34:

score: 0
Accepted
time: 5ms
memory: 3952kb

input:

2500 9 6
8 1 2 3 5 7 8 12 16
9 0 2 3 4 5 6 7 8 14
9 0 1 3 4 5 6 7 8 19
8 0 1 2 4 6 7 8 17
8 1 2 3 5 6 7 8 13
7 0 1 2 4 6 7 8
7 1 2 3 4 5 7 8
7 0 1 2 3 4 5 6
7 0 1 2 3 4 5 6
6 10 12 13 15 16 17
7 9 12 13 14 15 16 17
4 13 14 16 17
7 0 9 10 13 14 15 17
8 4 9 10 11 12 15 16 17
7 1 10 11 12 15 16 17
7 9 ...

output:

detention

result:

ok no solution