Submission #312626

#	Time	Username	Problem	Language	Result	Execution time	Memory
312626		joseacaz	Connecting Supertrees (IOI20_supertrees)	C++17	0 / 100	1 ms	384 KiB

supertrees

#include "supertrees.h"
#include <bits/stdc++.h>
#define pb push_back
#define all(x) x.begin(), x.end()

using namespace std;
using ll = long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
using vi = vector<int>;
using vl = vector<ll>;
using vpi = vector<pii>;
using vpl = vector<pll>;

const int MAXN = 1e3 + 5;
int N, par[MAXN], branch[MAXN];

int look(int node)
{
    if(par[node] == node)
        return node;
    return par[node] = look(par[node]);
}

void join(int a, int b)
{
    par[look(b)] = look(a);
}

int construct(vector<vi> p)
{
	N = p.size();
    vi branches, cycles;
    for(int i = 0; i < N; i++)
    {
        int one = 0, two = 0;
        for(int j = 0; j < N; j++)
        {
            if(i == j) continue;
            if(p[i][j] == 3)
                return 0;
            if(p[i][j] == 1)
                one++;
            if(p[i][j] == 2)
                two++;
        }
        
        //part of a branch
        if(one)
        {
            branches.pb(i);
            branch[i] = 1;
        }
        //part of the cycle
        else if(two)
            cycles.pb(i);
    }
    
	vector<vi> answer(N, vi(N, 0));
    for(int i = 0; i < N; i++)
        par[i] = i;
    for(auto i : branches)
    {
        if(look(i) != i)
            continue;

        int last = i;
        for(int j = 0; j < N; j++)
        {
            if(i == j) continue;
            if(p[i][j] == 1)
            {
                join(i, j);
                answer[last][j] = 1;
                answer[j][last] = 1;
                last = j;
            }
        }
        
        cycles.pb(i);
        branch[i] = 0;
    }
    
    for(int i = 0; i < N; i++)
        for(int j = 0; j < N; j++)
            if(i != j && p[i][j] != 1 && look(i) == look(j))
                return 0;
    
    for(int i = 0; i < N; i++)
        par[i] = i;
    for(auto i : cycles)
    {
        if(look(i) != i)
            continue;

        int last = i;
        for(int j = 0; j < N; j++)
        {
            if(i == j) continue;
            if(p[i][j] == 2 && !branch[j])
            {
                join(i, j);
                answer[last][j] = 1;
                answer[j][last] = 1;
                last = j;
            }
        }
        
        if(last != i)
        {
            answer[last][i] = 1;
            answer[i][last] = 1;
        }
        else
            return 0;
    }

    for(int i = 0; i < N; i++)
        for(int j = 0; j < N; j++)
            if(i != j && p[i][j] != 2 && look(i) == look(j))
                return 0;

    for(int i = 0; i < N; i++)
        for(int j = 0; j < N; j++)
            if(i != j && answer[i][j])
                join(i, j);
    for(int i = 0; i < N; i++)
        for(int j = 0; j < N; j++)
        {
            if(i != j && !p[i][j] && look(i) == look(j))
                return 0;
            if(i != j && p[i][j] && look(i) != look(j))
                return 0;
        }
    build(answer);
	return 1;
}

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