Submission #603601

#	Time	Username	Problem	Language	Result	Execution time	Memory
603601		Mher	Connecting Supertrees (IOI20_supertrees)	C++14	100 / 100	194 ms	28108 KiB

supertrees

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

using namespace std;

int n;
vector<vector<int>> a;
vector<int> col;
vector<vector<int>> r;
vector<int> gr;
vector<vector<int>> c;
vector<vector<int>> ans;

bool check()
{
    for (int i = 0; i < n; i++)
    {
        //cout << col[i] << ' ' << gr[col[i]] << endl;
        for (int j = 0; j < n; j++)
        {
            if (a[i][j] == 1)
            {
                if (col[i] != col[j])
                    return false;
            }
            else if (a[i][j] == 2)
            {
                if (col[i] == col[j] || gr[col[i]] != gr[col[j]])
                    return false;
            }
            else
            {
                if (col[i] == col[j] || gr[col[i]] == gr[col[j]])
                    return false;
            }
        }
    }
    for (int i = 0; i < c.size(); i++)
    {
        if (c[i].size() == 2)
            return false;
    }
    return true;
}

void conect(int v, int u)
{
    ans[v][u] = 1;
    ans[u][v] = 1;
}

void dfs(int v)
{
    for (int i = 0; i < n; i++)
    {
        if (i == v)
            continue;
        if (a[v][i] == 1 && col[i] == -1)
        {
            r[col[v]].push_back(i);
            col[i] = col[v];
            dfs(i);
        }
    }
}

void dfs2(int v)
{
    int u = r[v][0];
    for (int i = 0; i < r.size(); i++)
    {
        if (i == v)
            continue;
        int to = r[i][0];
        if (a[u][to] == 2 && gr[i] == -1)
        {
            c[gr[v]].push_back(i);
            gr[i] = gr[v];
            dfs2(i);
        }
    }
}

int construct(vector<vector<int>> p) {
	n = p.size();
	for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < n; j++)
        {
            if (p[i][j] == 3)
                return 0;
        }
    }
    a = p;
    ans = vector<vector<int>>(n, vector<int>(n, 0));
    int cnt = 0;
    col = vector<int>(n, -1);
    for (int i = 0; i < n; i++)
    {
        if (col[i] == -1)
        {
            r.push_back(vector<int>(1, i));
            col[i] = cnt++;
            dfs(i);
        }
    }
    cnt = 0;
    gr = vector<int>(r.size(), -1);
    for (int i = 0; i < r.size(); i++)
    {
        if (gr[i] == -1)
        {
            c.push_back(vector<int>(1, i));
            gr[i] = cnt++;
            dfs2(i);
        }
    }
    if (!check())
        return 0;
    for (int i = 0; i < r.size(); i++)
    {
        for (int j = 0; j < r[i].size() - 1; j++)
        {
            conect(r[i][j], r[i][j + 1]);
        }
    }
    for (int i = 0; i < c.size(); i++)
    {
        for (int j = 0; j < c[i].size() - 1; j++)
        {
            //cout << r[c[i][j]][0] << ' ' << r[c[i][j + 1]][0] << endl;
            conect(r[c[i][j]][0], r[c[i][j + 1]][0]);
        }
        if (c[i].size() != 1)
        {
            //cout << r[c[i][c[i].size() - 1]][0] << ' ' << r[c[i][0]][0] << endl;
            conect(r[c[i][c[i].size() - 1]][0], r[c[i][0]][0]);
        }
    }
    build(ans);
	return 1;
}

Compilation message (stderr)

supertrees.cpp: In function 'bool check()':
supertrees.cpp:39:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   39 |     for (int i = 0; i < c.size(); i++)
      |                     ~~^~~~~~~~~~
supertrees.cpp: In function 'void dfs2(int)':
supertrees.cpp:71:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   71 |     for (int i = 0; i < r.size(); i++)
      |                     ~~^~~~~~~~~~
supertrees.cpp: In function 'int construct(std::vector<std::vector<int> >)':
supertrees.cpp:110:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  110 |     for (int i = 0; i < r.size(); i++)
      |                     ~~^~~~~~~~~~
supertrees.cpp:121:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  121 |     for (int i = 0; i < r.size(); i++)
      |                     ~~^~~~~~~~~~
supertrees.cpp:123:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  123 |         for (int j = 0; j < r[i].size() - 1; j++)
      |                         ~~^~~~~~~~~~~~~~~~~
supertrees.cpp:128:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  128 |     for (int i = 0; i < c.size(); i++)
      |                     ~~^~~~~~~~~~
supertrees.cpp:130:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  130 |         for (int j = 0; j < c[i].size() - 1; j++)
      |                         ~~^~~~~~~~~~~~~~~~~

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