Submission #405974

#	Time	Username	Problem	Language	Result	Execution time	Memory
405974		tiberiu	Connecting Supertrees (IOI20_supertrees)	C++14	100 / 100	322 ms	24132 KiB

supertrees

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

using namespace std;

const int MAX_N = 1000;
int UF[MAX_N];

int root(int x) {
    return UF[x] == -1 ? x : UF[x] = root(UF[x]);
}

void unite(int x, int y) {
    x = root(x);
    y = root(y);

    if (x != y)
        UF[x] = y;
}

vector<vector<int>> b;

bool solve(const vector<vector<int>>& p, vector<int> c) {
    int N = p.size();

    for (int i : c)
        for (int j : c)
            if (p[i][j] == 1)
                unite(i, j);

    for (int i : c)
        for (int j : c)
            if (p[i][j] != 1 + (root(i) != root(j)))
                return 0;

    vector<int> cycle;
    for (int i : c)
        if (UF[i] != -1)
            b[i][UF[i]] = b[UF[i]][i] = 1;
        else
            cycle.push_back(i);

    if (cycle.size() == 2)
        return 0;
    if (cycle.size() > 1) {
        cycle.push_back(cycle[0]);
        for (int i = 1; i < cycle.size(); i++)
            b[cycle[i]][cycle[i-1]] = b[cycle[i-1]][cycle[i]] = 1;
    }

    return 1;
}

int construct(vector<vector<int>> p) {
    int N = p.size();
    for (int i = 0; i < N; i++)
        UF[i] = -1;
    for (int i = 0; i < N; i++)
        for (int j = 0; j < N; j++)
            if (p[i][j] == 3)
                return 0;
            else if (p[i][j])
                unite(i, j);

    vector<vector<int>> comps;
    for (int i = 0; i < N; i++)
        if (UF[i] == -1) {
            vector<int> c;
            for (int j = 0; j < N; j++)
                if (root(j) == i)
                    c.push_back(j);
            comps.push_back(c);
        }

    b.resize(N);
    for (int i = 0; i < N; i++) {
        UF[i] = -1;
        b[i].resize(N);
    }

    for (int i = 0; i < comps.size(); i++)
        if (!solve(p, comps[i]))
            return 0;

    build(b);
    return 1;
}

Compilation message (stderr)

supertrees.cpp: In function 'bool solve(const std::vector<std::vector<int> >&, std::vector<int>)':
supertrees.cpp:48:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   48 |         for (int i = 1; i < cycle.size(); i++)
      |                         ~~^~~~~~~~~~~~~~
supertrees.cpp:25:9: warning: unused variable 'N' [-Wunused-variable]
   25 |     int N = p.size();
      |         ^
supertrees.cpp: In function 'int construct(std::vector<std::vector<int> >)':
supertrees.cpp:82:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   82 |     for (int i = 0; i < comps.size(); i++)
      |                     ~~^~~~~~~~~~~~~~

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