Submission #319737

#	Time	Username	Problem	Language	Result	Execution time	Memory
319737		alextodoran	Connecting Supertrees (IOI20_supertrees)	C++17	100 / 100	265 ms	28132 KiB

supertrees

/**
 ____ ____ ____ ____ ____
||a |||t |||o |||d |||o ||
||__|||__|||__|||__|||__||
|/__\|/__\|/__\|/__\|/__\|

**/

#include <bits/stdc++.h>
#include "supertrees.h"

using namespace std;

typedef long long ll;

const int N_MAX = 1002;

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

int n;

vector <int> edges[N_MAX];

bool visited[N_MAX];

vector <int> aux;

void dfs (int u)
{
    visited[u] = true;
    aux.push_back(u);
    for(int v : edges[u])
        if(visited[v] == false)
            dfs(v);
}

bool chainRoot[N_MAX];

int chainIndex[N_MAX];
int cycleIndex[N_MAX];
int root[N_MAX];

int construct (vector <vector <int> > p)
{
    n = p.size();
    vector <vector <int> > answer;
    answer.resize(n);
    for(int i = 0; i < n; i++)
        answer[i].resize(n);
    for(int i = 0; i < n; i++)
        for(int j = 0; j < n; j++)
            answer[i][j] = false;
    for(int i = 0; i < n; i++)
        for(int j = 0; j < n; j++)
            if(p[i][j] == 3)
                return false;
    for(int i = 0; i < n; i++)
        for(int j = 0; j < n; j++)
            if(p[i][j] == 1)
                edges[i].push_back(j);
    int curr;
    curr = 0;
    for(int i = 0; i < n; i++)
        if(visited[i] == false)
        {
            dfs(i);
            chainRoot[i] = true;
            curr++;
            for(int j = 0; j < (int)aux.size(); j++)
                chainIndex[aux[j]] = curr;
            root[curr] = i;
            for(int j = 1; j < (int)aux.size(); j++)
                answer[aux[j - 1]][aux[j]] = answer[aux[j]][aux[j - 1]] = true;
            aux.clear();
        }
    for(int i = 0; i < n; i++)
    {
        edges[i].clear();
        visited[i] = false;
    }
    for(int i = 0; i < n; i++)
        for(int j = 0; j < n; j++)
            if(p[i][j] == 2)
                edges[i].push_back(j);
    for(int i = 0; i < n; i++)
        if(chainRoot[i] == false)
            visited[i] = true;
    curr = 0;
    for(int i = 0; i < n; i++)
        if(visited[i] == false)
        {
            dfs(i);
            chainRoot[i] = true;
            curr++;
            if((int)aux.size() == 2)
                return false;
            for(int j = 0; j < (int)aux.size(); j++)
                cycleIndex[aux[j]] = curr;
            for(int j = 0; j < (int)aux.size(); j++)
            {
                int j1 = j - 1;
                if(j == 0)
                    j1 += (int)aux.size();
                if(j != j1)
                    answer[aux[j1]][aux[j]] = answer[aux[j]][aux[j1]] = true;
            }
            aux.clear();
        }
    for(int i = 0; i < n; i++)
        for(int j = 0; j < n; j++)
            if(i != j)
            {
                int cnt = 0;
                if(cycleIndex[root[chainIndex[i]]] == cycleIndex[root[chainIndex[j]]] && chainIndex[i] != chainIndex[j])
                    cnt = 2;
                else if(chainIndex[i] == chainIndex[j])
                    cnt = 1;
                else
                    cnt = 0;
                if(cnt != p[i][j])
                    return false;
            }
    build(answer);
    return true;
}

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