Code Submission Evaluation System Login

BOI 2016, day 1

Start:2016-05-12 09:00:00
End:2016-05-12 14:00:00
 

Tasks | Scoreboard | Statistics


CSES - BOI 2016, day 1 - Results
History
2016-05-12 10:18:59100
2016-05-12 10:17:0167
2016-05-12 10:14:2467
2016-05-12 10:11:3667
Task:Bosses
Sender:vladmosko
Submission time:2016-05-12 10:18:59
Language:C++
Status:READY
Score:100

Feedback

groupverdictscore
#1ACCEPTED22
#2ACCEPTED45
#3ACCEPTED33

Test results

testverdicttime (s)group
#1ACCEPTED0.04 / 1.501details
#2ACCEPTED0.07 / 1.501details
#3ACCEPTED0.06 / 1.501details
#4ACCEPTED0.06 / 1.501details
#5ACCEPTED0.06 / 1.501details
#6ACCEPTED0.05 / 1.501details
#7ACCEPTED0.05 / 1.502details
#8ACCEPTED0.06 / 1.502details
#9ACCEPTED0.06 / 1.502details
#10ACCEPTED0.06 / 1.502details
#11ACCEPTED0.05 / 1.502details
#12ACCEPTED0.06 / 1.503details
#13ACCEPTED0.06 / 1.503details
#14ACCEPTED0.06 / 1.503details
#15ACCEPTED0.05 / 1.503details
#16ACCEPTED0.06 / 1.503details
#17ACCEPTED0.06 / 1.503details
#18ACCEPTED0.06 / 1.503details

Compiler report

input/code.cpp: In function 'int main()':
input/code.cpp:79:20: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &n);
                    ^
input/code.cpp:83:24: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d", &t);
                        ^
input/code.cpp:85:28: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
             scanf("%d", &x);
                            ^

Code

#include <iostream>
#include <set>
#include <map>
#include <string>
#include <vector>
#include <bitset>
#include <algorithm>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <stack>
#include <cstdio>
#include <cassert>
#include <ctime>
#include <queue>
#include <numeric>

using namespace std;

typedef long long ll;
typedef long double ld;

int n, t, i, x, ans;
vector<int> hang[5005];
bool active[5005];
int deg[5005];
int rid[5005];
vector<int> in[5005];
vector<int> gph[5005];

bool cmp(int i, int j) {
    return deg[i] > deg[j];
}

void deactivate(int x) {
    if (!active[x])
        return;
    active[x] = false;
    for (int i = 0; i < (int)in[x].size(); i++)
        deg[in[x][i]]--;
}

void run(int y) {
    queue<int> q;
    q.push(y);
    while (!q.empty()) {
        int x = q.front();
        deactivate(x);
        q.pop();
        vector<int> ch;
        for (int i = 0; i < (int)hang[x].size(); i++) {
            int c = hang[x][i];
            if (!active[c])
                continue;
            gph[x].push_back(c);
            deactivate(c);
            ch.push_back(c);
        }
        sort(ch.begin(), ch.end(), cmp);
        for (int i = 0; i < (int)ch.size(); i++)
            q.push(ch[i]);
    }
}

bool mem[5005];
int ret[5005];

int calc(int x) {
    if (mem[x])
        return ret[x];
    mem[x] = true;
    int s = 0;
    for (int i = 0; i < (int)gph[x].size(); i++)
        s += calc(gph[x][i]);
    return ret[x] = s + 1;
}

int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; i++)
        hang[i].clear();
    for (int i = 1; i <= n; i++) {
        scanf("%d", &t);
        while (t--) {
            scanf("%d", &x);
            hang[x].push_back(i);
            in[i].push_back(x);
        }
    }
    for (int i = 1; i <= n; i++) {
        sort(hang[i].begin(), hang[i].end());
        hang[i].resize(unique(hang[i].begin(), hang[i].end()) - hang[i].begin());
        deg[i] = (int)hang[i].size();
    }
    ans = (int)2e9;
    int L = 1;
    int R = min(20, n);
    for (int i = 1; i <= n; i++)
        if ((int)in[i].size() == 0)
            L = R = i;
    for (int i = 1; i <= n; i++)
        rid[i] = i;
    sort(rid + 1, rid + n + 1, cmp);
    for (int j = L; j <= R; j++) {
        int root = rid[j];
        if (L == R)
            root = L;
        memset(active, true, sizeof(active));
        for (int i = 1; i <= n; i++)
            gph[i].clear();
        run(root);
        bool good = true;
        for (int i = 1; i <= n; i++)
            if (active[i]) {
                good = false;
                break;
            }
        if (!good) continue;
        int ss = 0;
        memset(mem, 0, sizeof(mem));
        for (int i = 1; i <= n; i++)
            ss += calc(i);
        ans = min(ans, ss);
    }
    printf("%d\n", ans);
    return 0;
}

Test details

Test 1

Group: 1

Verdict: ACCEPTED

input
4
1 4
3 1 3 4
2 1 2
1 3
view   save

correct output
8

view   save

user output
8

view   save

Test 2

Group: 1

Verdict: ACCEPTED

input
6
2 6 5
3 4 6 3
2 4 1
4 5 3 1 6
...
view   save

correct output
12

view   save

user output
12

view   save

Test 3

Group: 1

Verdict: ACCEPTED

input
9
2 6 3
2 8 4
0
4 8 3 6 9
...
view   save

correct output
22

view   save

user output
22

view   save

Test 4

Group: 1

Verdict: ACCEPTED

input
10
3 3 2 8
3 6 7 3
4 6 10 7 9
1 10
...
view   save

correct output
24

view   save

user output
24

view   save

Test 5

Group: 1

Verdict: ACCEPTED

input
10
3 4 8 10
1 10
1 5
3 6 8 5
...
view   save

correct output
23

view   save

user output
23

view   save

Test 6

Group: 1

Verdict: ACCEPTED

input
10
2 2 6
2 3 5
2 4 1
2 6 7
...
view   save

correct output
26

view   save

user output
26

view   save

Test 7

Group: 2

Verdict: ACCEPTED

input
100
2 78 92
1 15
1 57
1 45
...
view   save

correct output
527

view   save

user output
527

view   save

Test 8

Group: 2

Verdict: ACCEPTED

input
50
6 16 31 50 6 4 8
7 7 16 27 22 15 30 14
5 20 22 42 33 37
3 18 45 9
...
view   save

correct output
156

view   save

user output
156

view   save

Test 9

Group: 2

Verdict: ACCEPTED

input
30
5 12 26 25 18 24
8 6 13 5 7 10 22 20 29
6 16 14 9 27 5 20
3 19 17 11
...
view   save

correct output
77

view   save

user output
77

view   save

Test 10

Group: 2

Verdict: ACCEPTED

input
100
2 2 77
3 99 94 85
2 47 29
2 33 74
...
view   save

correct output
428

view   save

user output
428

view   save

Test 11

Group: 2

Verdict: ACCEPTED

input
100
3 50 11 85
2 84 69
2 41 39
2 43 82
...
view   save

correct output
617

view   save

user output
617

view   save

Test 12

Group: 3

Verdict: ACCEPTED

input
200
46 154 36 47 187 86 48 66 124 ...
view   save

correct output
531

view   save

user output
531

view   save

Test 13

Group: 3

Verdict: ACCEPTED

input
150
60 32 101 42 139 95 36 81 83 1...
view   save

correct output
370

view   save

user output
370

view   save

Test 14

Group: 3

Verdict: ACCEPTED

input
5000
1 3355
1 2176
1 3754
1 950
...
view   save

correct output
6256017

view   save

user output
6256017

view   save

Test 15

Group: 3

Verdict: ACCEPTED

input
5000
1 848
1 418
1 3390
1 2840
...
view   save

correct output
45193

view   save

user output
45193

view   save

Test 16

Group: 3

Verdict: ACCEPTED

input
5000
2 4629 753
1 345
3 3573 1802 449
1 3051
...
view   save

correct output
27449

view   save

user output
27449

view   save

Test 17

Group: 3

Verdict: ACCEPTED

input
5000
2 2282 1819
2 2987 3194
2 3472 4256
2 3226 3684
...
view   save

correct output
39850

view   save

user output
39850

view   save

Test 18

Group: 3

Verdict: ACCEPTED

input
5000
2 1912 3423
2 419 4226
2 1627 4693
2 4760 1391
...
view   save

correct output
40097

view   save

user output
40097

view   save