Submission #1047611

#	Time	Username	Problem	Language	Result	Execution time	Memory
1047611		idas	Connecting Supertrees (IOI20_supertrees)	C++17	100 / 100	112 ms	24148 KiB

supertrees

#include "supertrees.h"
#include "bits/stdc++.h"
#define FOR(i, begin, end) for(int i=(begin); i<(end); i++)
#define sz(x) ((int)((x).size()))
#define pb push_back

using namespace std;
typedef long long ll;
typedef vector<int> vi;

const int MxN=1e3+10;
int n, par[MxN], cyc[MxN];
bool v[MxN];

int fnd(int u) {
    return par[u]=par[u]==u?u:fnd(par[u]);
}

void mrg(int a, int b) {
    a=fnd(a); b=fnd(b);
    if(a==b) return;
    par[a]=b;
}

int construct(std::vector<std::vector<int>> p) {
    n=sz(p);

    FOR(i, 0, n) par[i]=i;

    vector b(n, vector(n, 0));
    FOR(i, 0, n) {
        FOR(j, 0, n) {
            if(fnd(i)==fnd(j)) continue;
            if(p[i][j]==1) {
                b[i][j]=b[j][i]=1;
                mrg(i, j);
            }
        }
    }

    vector used(n, false);
    FOR(i, 0, n) {
        int u=fnd(i);
        if(used[u]) continue;

        used[u]=true;
        cyc[u]=i;

        int cn=1, lst=u, frst=u;
        FOR(j, 0, n) {
            int w=fnd(j);
            if(used[w]) continue;

            if(p[u][w]==2) {
                used[w]=true;
                cyc[w]=i;
                cn++;

                b[lst][w]=b[w][lst]=1;
                lst=w;
            }
        }
        b[lst][frst]=b[frst][lst]=1;

        if(cn==2) {
            return 0;
        }
    }

    bool ok=true;
    FOR(i, 0, n) {
        FOR(j, i+1, n) {
            int u=fnd(i), w=fnd(j);
            if(u==w) ok&=p[i][j]==1;
            else if(cyc[u]==cyc[w]) ok&=p[i][j]==2;
            else ok&=p[i][j]==0;
        }
    }

    FOR(i, 0, n) b[i][i]=0;

    if(!ok) return 0;

    build(b);

    return 1;
}
/*
Example 1:
4
1 1 2 2
1 1 2 2
2 2 1 2
2 2 2 1

Example 2:
2
1 0
0 1

Example 3:
2
1 3
3 1

5
1 1 2 2 2
1 1 2 2 2
2 2 1 2 2
2 2 2 1 1
2 2 2 1 1
*/

• Subtask 1: 11 / 11
• Subtask 2: 10 / 10
• Subtask 3: 19 / 19
• Subtask 4: 35 / 35
• Subtask 5: 21 / 21
• Subtask 6: 4 / 4