Submission #313564

#	Time	Username	Problem	Language	Result	Execution time	Memory
313564		mohamedsobhi777	Connecting Supertrees (IOI20_supertrees)	C++14	0 / 100	1 ms	256 KiB

supertrees

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

using namespace std;

std::vector<std::vector<int>> answer, p ; 
int vis[100000];
bool bad;
int nn;

vector<int> vecs(int x)
{
        vector<int> ret;
        queue<int> qu;
        qu.push(x);
        while (qu.size())
        {
                int x = qu.front();
                qu.pop();
                if (vis[x]++)
                        continue;
                ret.push_back(x);
                for (int i = 0; i < nn; ++i)
                {
                        if (i == x || vis[i] || !p[x][i])
                                continue;
                        qu.push(i);
                }
        }
        return ret;
}

void solve(vector<int> vecs)
{
        if (!vecs.size())
                return;
        int sz = (int)vecs.size();
        vector<int> cycle, line;
        for (int i = 0; i < sz; ++i)
        {
                int cir = 1; 
                for (int j = 0; j < sz; ++j)
                {
                        if (i == j)
                                continue;
                        cir += (p[vecs[i]][vecs[j]] == 2) ; 
                }
                if (cir == (int)vecs.size() && vecs.size() > 2)
                        cycle.push_back(i);
        }
        if (cycle.size() == 1)
                bad = 1;
        if (line.size() && cycle.size())
                cycle.push_back(line[0]);
        for (int i = 0; i < (int)cycle.size(); ++i)
        {
        }
        for (int i = 1; i < (int)line.size(); ++i)
        {
                int x = vecs[line[i]], y = vecs[line[i - 1]];
                answer[x][y] = answer[y][x] = 1;
        }
        for (int i = 0; i < line.size(); ++i)
        {
                for (int j = 0; j < line.size(); ++j)
                {
                        if (i == j)
                                continue;
                        if (p[vecs[i]][vecs[j]] != 1)
                                bad = 1;
                }
        }
}

int construct(std::vector<std::vector<int>> P)
{
        p = P ; 
        nn = p.size();
        for (int i = 0; i < nn; i++)
        {
                std::vector<int> row;
                row.resize(nn);
                answer.push_back(row);
        }
        for (int i = 0; i < nn; ++i)
        {
                vector<int> g = vecs(i);
                solve(g);
        }
        if (bad)
                return 0;
        build(answer);
        return 1;
}

Compilation message (stderr)

supertrees.cpp: In function 'void solve(std::vector<int>)':
supertrees.cpp:64:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   64 |         for (int i = 0; i < line.size(); ++i)
      |                         ~~^~~~~~~~~~~~~
supertrees.cpp:66:35: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   66 |                 for (int j = 0; j < line.size(); ++j)
      |                                 ~~^~~~~~~~~~~~~

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