제출 #420385

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
420385		idk321	슈퍼트리 잇기 (IOI20_supertrees)	C++17	56 / 100	304 ms	30436 KiB

supertrees

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

using namespace std;
#include <bits/stdc++.h>

vector<vector<int>> p;
vector<vector<int>> groups;
vector<vector<int>> answer;
vector<vector<int>> relation1;
vector<int> isIn;
vector<int> isInGroup;
int n;
int ng;
void dfs(int node, int cur, int par)
{
    isIn[node] = cur;
    groups[cur].push_back(node);
    if (par != -1)
    {
        answer[node][par] = 1;
        answer[par][node] = 1;
    }

    for (int i = 0; i < n; i++)
    {
        if (isIn[i] == -1 && p[node][i] == 1)
        {
            dfs(i, cur, node);
        }
    }
}

void dfs2(int node, int cur)
{
    isInGroup[node] = cur;
    groups[cur].push_back(node);



    for (int i = 0; i < ng; i++)
    {
        if (isInGroup[i] == -1 && relation1[node][i] == 2)
        {
            dfs2(i, cur);
        }
    }
}

int construct(std::vector<std::vector<int>> P) {
    p = P;
	n = p.size();
    for (int i = 0; i < n; i++)
    {
        for (int j = i; j < n; j++)
        {
            if (p[i][j] >= 3) return 0;
        }
    }



    isIn.resize(n, -1);
    answer.resize(n, vector<int>(n));

    int cur = 0;
    for (int i = 0; i < n; i++)
    {
        if (isIn[i] == -1)
        {
            groups.push_back(vector<int>());
            dfs(i, cur, -1);
            cur++;
        }
    }

    for (auto g : groups)
    {
        for (int i = 0; i < g.size(); i++)
        {
            for (int j = i + 1; j < g.size(); j++)
            {
                if (p[g[i]][g[j]] != 1) return 0;
            }
        }
    }
    ng = groups.size();


    relation1.resize(n, vector<int>(n, -1));
    for (int i = 0; i < n; i++)
    {
        for (int j = i + 1; j < n; j++)
        {
            if (isIn[i] != isIn[j])
            {
                if (relation1[isIn[i]][isIn[j]] == -1)
                {
                    relation1[isIn[i]][isIn[j]] = p[i][j];
                    relation1[isIn[j]][isIn[i]] = p[i][j];
                } else if (relation1[isIn[i]][isIn[j]] != p[i][j]) return 0;
            }
        }
    }

    isInGroup.resize(n, -1);
    groups.clear();
    cur = 0;
    for (int i = 0; i < ng; i++)
    {
        if (isInGroup[i] == -1)
        {
            groups.push_back(vector<int>());
            dfs2(i, cur);
            cur++;
        }
    }

    vector<int> nodeInGroup(ng);
    for (int i = 0; i < n; i++)
    {
        nodeInGroup[isIn[i]] = i;
    }

    for (auto g : groups)
    {
        if (g.size() <= 2) continue;

        for (int i = 0; i < g.size(); i++)
        {
            for (int j = i + 1; j < g.size(); j++)
            {
                if (relation1[g[i]][g[j]] != 2) return 0;
            }

            int a = i;
            int b = (i + 1) % g.size();
            answer[nodeInGroup[g[a]]][nodeInGroup[g[b]]] = 1;
            answer[nodeInGroup[g[b]]][nodeInGroup[g[a]]] = 1;
        }
    }



	build(answer);

	return 1;
}

컴파일 시 표준 에러 (stderr) 메시지

supertrees.cpp: In function 'int construct(std::vector<std::vector<int> >)':
supertrees.cpp:79:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   79 |         for (int i = 0; i < g.size(); i++)
      |                         ~~^~~~~~~~~~
supertrees.cpp:81:35: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   81 |             for (int j = i + 1; j < g.size(); j++)
      |                                 ~~^~~~~~~~~~
supertrees.cpp:129:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  129 |         for (int i = 0; i < g.size(); i++)
      |                         ~~^~~~~~~~~~
supertrees.cpp:131:35: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  131 |             for (int j = i + 1; j < g.size(); j++)
      |                                 ~~^~~~~~~~~~

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