제출 #309345

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
309345		mihai145	슈퍼트리 잇기 (IOI20_supertrees)	C++14	11 / 100	273 ms	34172 KiB

supertrees

#include "supertrees.h"
#include <vector>
#include <iostream>

const int NMAX = 1000;

std::vector <std::pair <int, int> > edges;

std::vector <std::vector <int>> input;

int N;
std::vector <std::pair <int, int>> g[NMAX + 1];

bool seen[NMAX + 1];

int nrComp;
std::vector <int> comp[NMAX + 1];

void dfsComp(int node)
{
    seen[node] = true;
    comp[nrComp].push_back(node);

    for(auto it : g[node])
        if(!seen[it.first])
            dfsComp(it.first);
}

int kId, chainId[NMAX + 1];
std::vector < int > currentChain;

void dfs(int node, int par)
{
    chainId[node] = kId;
    currentChain.push_back(node);

    if(par != -1)
        edges.push_back({par, node});

    for(auto it : g[node])
        if(chainId[it.first] == 0 && it.second == 1)
            dfs(it.first, node);
}

bool SolveComp(int c)
{
    kId = 0;
    std::vector <int> representatives;

    for(auto node : comp[c])
        if(chainId[node] == 0)
            {
                ++kId;
                currentChain.clear();
                dfs(node, -1);
                representatives.push_back(currentChain[0]);
            }

    if((int)representatives.size() == 2)
        return 0;

    if((int)representatives.size() > 2)
    {
        for(int i = 1; i < (int)representatives.size(); i++)
            edges.push_back({representatives[i], representatives[i - 1]});
        edges.push_back({representatives[0], representatives.back()});
    }

    for(int i = 0; i < (int)comp[c].size(); i++)
        for(int j = 0; j < (int)comp[c].size(); j++)
            if(i != j)
                {
                    if(chainId[i] != chainId[j])
                        {
                            if(input[i][j] != 2)
                                return false;
                        }
                    else
                        {
                            if(input[i][j] != 1)
                                return false;
                        }
                }

    return true;
}

int construct(std::vector<std::vector<int>> p) {
	input = p;
	N = p.size();

	for(int i = 0; i < N; i++)
        for(int j = 0; j < N; j++)
            if(i != j && p[i][j] > 0)
                {
                    if(p[i][j] == 3)
                        return 0;

                    g[i].push_back({j, p[i][j]});
                }

    for(int i = 0; i < N; i++)
        if(!seen[i])
            {
                nrComp++;
                dfsComp(i);
            }

    bool haveSol = true;
    for(int i = 1; i <= nrComp; i++)
        {
            haveSol &= SolveComp(i);
            if(!haveSol)
                return 0;
        }

	std::vector<std::vector<int>> answer;
	for (int i = 0; i < N; i++) {
		std::vector<int> row;
		row.resize(N);
		answer.push_back(row);
	}

	for(auto it : edges)
        answer[it.first][it.second] = answer[it.second][it.first] = 1;

	build(answer);
	return 1;
}

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