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:15:05100
2016-05-12 10:14:0767
2016-05-12 10:13:3167
2016-05-12 10:09:3767
2016-05-12 10:05:160
2016-05-12 10:01:1367
2016-05-12 10:00:3667
2016-05-12 09:56:5567
2016-05-12 09:52:1667
Task:Bosses
Sender:bogdan10bos
Submission time:2016-05-12 10:15:05
Language:C++
Status:READY
Score:100

Feedback

groupverdictscore
#1ACCEPTED22
#2ACCEPTED45
#3ACCEPTED33

Test results

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

Compiler report

input/code.cpp: In function 'int main()':
input/code.cpp:117:55: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
                     if(f[ft] == h && nxt[ft].size() < sns)
                                                       ^
input/code.cpp: In function 'char gchar()':
input/code.cpp:16:38: warning: ignoring return value of 'size_t fread(void*, size_t, size_t, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
         fread(buff, buffer, 1, stdin);
                                      ^

Code

#include <bits/stdc++.h>

using namespace std;

//#define FILE_IO

const int buffer = 1 << 14;
int cnt = buffer - 1;
char buff[buffer + 5];

char gchar()
{
    if(++cnt == buffer)
    {
        cnt = 0;
        fread(buff, buffer, 1, stdin);
    }
    return buff[cnt];
}

int gint()
{
    char ch = gchar();
    while(ch < '0' || '9' < ch)
        ch = gchar();
    int x = 0;
    while('0' <= ch && ch <= '9')
    {
        x = x * 10 + ch - '0';
        ch = gchar();
    }
    return x;
}

int N, sum;
int f[5005];
vector <int> chd[5005];
vector <int> bos[5005];
vector <int> nds[5005];
vector <int> nxt[5005];

int can[5005];
int b[5005][5005];
int father[5005];
int val[5005];
int fii[5005];

bool cmp(int a, int b)
{
    return (chd[a].size() > chd[b].size());
}

void DFS(int nod)
{
    val[nod] = 1;
    for(auto son: nxt[nod])
        DFS(son);
    val[father[nod]] += val[nod];
    sum += val[nod];
}

int main()
{
    #ifdef FILE_IO
    freopen("1.in", "r", stdin);
    freopen("1.out", "w", stdout);
    #endif

    srand(time(0));

    N = gint();
    for(int i = 1; i <= N; i++)
    {
        fii[i] = i;
        int M;
        M = gint();
        for(int j = 1; j <= M; j++)
        {
            int x;
            x = gint();
            b[i][x] = 1;
            bos[i].push_back(x);
            chd[x].push_back(i);
        }
    }

    sort(fii + 1, fii + N + 1, cmp);

    int ans = 1 << 30;
    //for(int root = 1; root <= N; root++)
    for(int tm = 1; tm <= 2300; tm++)
    {
        int root = fii[tm];
        memset(f, 0, sizeof(f));
        for(int i = 1; i <= N; i++)
        {
            nds[i].clear();
            nxt[i].clear();
        }

        nds[1].push_back(root);
        f[root] = 1;
        father[root] = 0;
        int rem = N - 1;
        for(int h = 1; h <= N && rem; h++)
        {
            if(nds[h].size() == 0)  break;
            for(auto i: nds[h])
                for(auto j: chd[i])
                    if(!f[j])
                        nds[h + 1].push_back(j), f[j] = h + 1, rem--;
            for(auto nod: nds[h + 1])
            {
                int fth = 0;
                int sns = 1 << 30;
                for(auto ft: bos[nod])
                    if(f[ft] == h && nxt[ft].size() < sns)
                    {
                        sns = nxt[ft].size();
                        fth = ft;
                    }
                nxt[fth].push_back(nod);
                father[nod] = fth;
            }
        }
        if(rem) continue;
        sum = 0;
        DFS(root);
        if(sum < ans)
            ans = sum;
    }
    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