Submission #503200

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
503200	2022-01-07T13:27:51 Z	LouayFarah	Connecting Supertrees (IOI20_supertrees)	C++14	30 / 100	208 ms	22092 KB

supertrees

#include "bits/stdc++.h"

using namespace std;

#define endl "\n"
#define ll long long int
#define pb push_back
#define mp make_pair
#define fi first
#define se second

const long long MOD = 1e9+7;
const long long INF = 1e18;

int nx[4] = {0, 0, -1, 1};
int ny[4] = {1, -1, 0, 0};

void build(vector<vector<int>> b);

struct dsu
{
    vector<int> len;
    vector<int> link;

    void init(int n)
    {
        len.assign(n, 1);
        link.assign(n, 0);
        for(int i = 0; i<n; i++)
        {
            link[i] = i;
        }
    }

    int search(int x)
    {
        if(x!=link[x])
            link[x] = search(link[x]);
        return link[x];
    }

    bool check(int a, int b)
    {
        return search(a)==search(b);
    }

    void join(int a, int b)
    {
        a = search(a);
        b = search(b);

        if(a!=b)
        {
            if(len[a]<len[b])
                swap(a, b);

            len[a]+=len[b];
            link[b] = a;
        }
    }
};

int construct(vector<vector<int>> p)
{
    int n = int(p[0].size());

    vector<vector<int>> b(n, vector<int>(n, 0));

    dsu d;
    d.init(n);

    bool flag1 = false;
    bool flag2 = true;

    for(int i = 0; i<n; i++)
    {
        for(int j = i+1; j<n; j++)
        {
            if(p[i][j]==1)
            {
                d.join(i, j);
                flag1 = true;
            }
            if(p[i][j]==2)
            {
                d.join(i, j);
                flag2 = true;
            }
        }
    }

    vector<vector<int>> groups(n);
    for(int i = 0; i<n; i++)
    {
        int parent = d.search(i);
        groups[parent].pb(i);
    }

    /*for(int i = 0; i<n; i++)
    {
        cout << i << ": ";
        for(auto elt: groups[i])
            cout << elt << ' ';
        cout << endl;
    }*/


    if(!flag2&&flag1)
    {
        for(int i = 0; i<n; i++)
        {
            if(groups[i].empty())
                continue;

            int len = int(groups[i].size());
            for(int j = 0; j<len-1; j++)
            {

                int A = groups[i][j];
                int B = groups[i][j+1];

                b[A][B] = 1;
                b[B][A] = 1;
            }
        }
    }
    else if(!flag1&&flag2)
    {
        for(int i = 0; i<n; i++)
        {
            if(groups[i].empty())
                continue;

            if(int(groups[i].size())==2)
                return 0;

            int len = int(groups[i].size());
            for(int j = 0; j<len-1; j++)
            {

                int A = groups[i][j];
                int B = groups[i][j+1];

                b[A][B] = 1;
                b[B][A] = 1;
            }
            int A = groups[i][len-1];
            int B = groups[i][0];

            b[A][B] = 1;
            b[B][A] = 1;
        }
    }
    else
    {
        for(auto group: groups)
        {
            if(group.empty())
                continue;


            vector<int> one, two;
            int len = int(group.size());
            for(int i = 0; i<len; i++)
            {
                int A = group[i];
                bool only2 = true;
                for(int j = 0; j<len; j++)
                {
                    if(i==j)
                        continue;
                    int B = group[j];
                    if(p[A][B]==1)
                    {
                        only2 = false;
                        break;
                    }
                }

                if(only2)
                    two.pb(i);
                else
                    one.pb(i);
            }

            if(two.empty())
            {
                for(int j = 0; j<int(one.size())-1; j++)
                {

                    int A = one[j];
                    int B = one[j+1];

                    b[A][B] = 1;
                    b[B][A] = 1;
                }
            }
            else if(one.empty())
            {
                if(int(two.size())==2)
                    return 0;
                for(int j = 0; j<int(two.size())-1; j++)
                {
                    int A = two[j];
                    int B = two[j+1];

                    b[A][B] = 1;
                    b[B][A] = 1;
                }
                int A = two[int(two.size())-1];
                int B = two[0];

                b[A][B] = 1;
                b[B][A] = 1;
            }
            else
            {
                for(int j = 0; j<int(one.size())-1; j++)
                {

                    int A = one[j];
                    int B = one[j+1];

                    b[A][B] = 1;
                    b[B][A] = 1;
                }

                for(int j = 0; j<int(two.size())-1; j++)
                {
                    int A = two[j];
                    int B = two[j+1];

                    b[A][B] = 1;
                    b[B][A] = 1;
                }

                int A = one[0];
                int B = two[0];
                int C = two[int(two.size())-1];

                b[A][B] = 1;
                b[B][A] = 1;
                b[A][C] = 1;
                b[C][A] = 1;
            }
        }
    }

    for(int i = 0; i<n; i++)
    {
        for(int j = i+1; j<n; j++)
        {
            if(p[i][j]==0&&d.check(i, j))
                return 0;
            if(!d.check(i, j)&&p[i][j]!=0)
                return 0;
        }
    }

    for(int i = 0; i<n; i++)
    {
        b[i][i]  = 0;
    }

    build(b);
    return 1;
}

Subtask #1
11.0 / 11.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	204 KB	Output is correct
2	Correct	0 ms	204 KB	Output is correct
3	Correct	0 ms	204 KB	Output is correct
4	Correct	0 ms	204 KB	Output is correct
5	Correct	0 ms	204 KB	Output is correct
6	Correct	7 ms	1100 KB	Output is correct
7	Correct	169 ms	22092 KB	Output is correct

Subtask #2
0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	204 KB	Output is correct
2	Correct	0 ms	204 KB	Output is correct
3	Correct	0 ms	204 KB	Output is correct
4	Correct	0 ms	204 KB	Output is correct
5	Correct	0 ms	204 KB	Output is correct
6	Correct	7 ms	1100 KB	Output is correct
7	Correct	169 ms	22092 KB	Output is correct
8	Correct	0 ms	204 KB	Output is correct
9	Correct	0 ms	204 KB	Output is correct
10	Correct	0 ms	204 KB	Output is correct
11	Correct	0 ms	204 KB	Output is correct
12	Correct	7 ms	1132 KB	Output is correct
13	Correct	168 ms	22024 KB	Output is correct
14	Correct	0 ms	204 KB	Output is correct
15	Correct	0 ms	204 KB	Output is correct
16	Correct	4 ms	716 KB	Output is correct
17	Correct	79 ms	12156 KB	Output is correct
18	Correct	1 ms	256 KB	Output is correct
19	Correct	0 ms	204 KB	Output is correct
20	Incorrect	42 ms	5756 KB	Too many ways to get from 0 to 1, should be 0 found no less than 1
21	Halted	0 ms	0 KB	-

Subtask #3
19.0 / 19.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	204 KB	Output is correct
2	Correct	0 ms	204 KB	Output is correct
3	Correct	0 ms	204 KB	Output is correct
4	Correct	0 ms	204 KB	Output is correct
5	Correct	0 ms	220 KB	Output is correct
6	Correct	0 ms	204 KB	Output is correct
7	Correct	0 ms	212 KB	Output is correct
8	Correct	7 ms	1124 KB	Output is correct
9	Correct	173 ms	22008 KB	Output is correct
10	Correct	0 ms	204 KB	Output is correct
11	Correct	0 ms	204 KB	Output is correct
12	Correct	7 ms	1152 KB	Output is correct
13	Correct	169 ms	22024 KB	Output is correct
14	Correct	0 ms	204 KB	Output is correct
15	Correct	0 ms	204 KB	Output is correct
16	Correct	7 ms	712 KB	Output is correct
17	Correct	84 ms	12112 KB	Output is correct
18	Correct	0 ms	204 KB	Output is correct
19	Correct	0 ms	204 KB	Output is correct
20	Correct	0 ms	204 KB	Output is correct
21	Correct	42 ms	5760 KB	Output is correct
22	Correct	182 ms	22012 KB	Output is correct
23	Correct	172 ms	22076 KB	Output is correct
24	Correct	198 ms	22008 KB	Output is correct
25	Correct	71 ms	12168 KB	Output is correct
26	Correct	73 ms	12156 KB	Output is correct
27	Correct	171 ms	22012 KB	Output is correct
28	Correct	208 ms	22024 KB	Output is correct
29	Correct	77 ms	12152 KB	Output is correct

Subtask #4
0 / 35.0

#	Verdict	Memory	Grader output
1	Correct	204 KB	Output is correct
2	Correct	204 KB	Output is correct
3	Incorrect	204 KB	Too many ways to get from 0 to 1, should be 0 found no less than 1
4	Halted	0 KB	-

Subtask #5
0 / 21.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	204 KB	Output is correct
2	Correct	0 ms	204 KB	Output is correct
3	Correct	0 ms	204 KB	Output is correct
4	Correct	0 ms	204 KB	Output is correct
5	Correct	0 ms	204 KB	Output is correct
6	Correct	7 ms	1100 KB	Output is correct
7	Correct	169 ms	22092 KB	Output is correct
8	Correct	0 ms	204 KB	Output is correct
9	Correct	0 ms	204 KB	Output is correct
10	Correct	0 ms	204 KB	Output is correct
11	Correct	0 ms	204 KB	Output is correct
12	Correct	7 ms	1132 KB	Output is correct
13	Correct	168 ms	22024 KB	Output is correct
14	Correct	0 ms	204 KB	Output is correct
15	Correct	0 ms	204 KB	Output is correct
16	Correct	4 ms	716 KB	Output is correct
17	Correct	79 ms	12156 KB	Output is correct
18	Correct	1 ms	256 KB	Output is correct
19	Correct	0 ms	204 KB	Output is correct
20	Incorrect	42 ms	5756 KB	Too many ways to get from 0 to 1, should be 0 found no less than 1
21	Halted	0 ms	0 KB	-

Subtask #6
0 / 4.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	204 KB	Output is correct
2	Correct	0 ms	204 KB	Output is correct
3	Correct	0 ms	204 KB	Output is correct
4	Correct	0 ms	204 KB	Output is correct
5	Correct	0 ms	204 KB	Output is correct
6	Correct	7 ms	1100 KB	Output is correct
7	Correct	169 ms	22092 KB	Output is correct
8	Correct	0 ms	204 KB	Output is correct
9	Correct	0 ms	204 KB	Output is correct
10	Correct	0 ms	204 KB	Output is correct
11	Correct	0 ms	204 KB	Output is correct
12	Correct	7 ms	1132 KB	Output is correct
13	Correct	168 ms	22024 KB	Output is correct
14	Correct	0 ms	204 KB	Output is correct
15	Correct	0 ms	204 KB	Output is correct
16	Correct	4 ms	716 KB	Output is correct
17	Correct	79 ms	12156 KB	Output is correct
18	Correct	1 ms	256 KB	Output is correct
19	Correct	0 ms	204 KB	Output is correct
20	Incorrect	42 ms	5756 KB	Too many ways to get from 0 to 1, should be 0 found no less than 1
21	Halted	0 ms	0 KB	-

Submission #503200

Compilation message

Subtask #1 11.0 / 11.0

Subtask #2 0 / 10.0

Subtask #3 19.0 / 19.0

Subtask #4 0 / 35.0

Subtask #5 0 / 21.0

Subtask #6 0 / 4.0

Subtask #1
11.0 / 11.0

Subtask #2
0 / 10.0

Subtask #3
19.0 / 19.0

Subtask #4
0 / 35.0

Subtask #5
0 / 21.0

Subtask #6
0 / 4.0