Submission #313595

#	Time	Username	Problem	Language	Result	Execution time	Memory
313595		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, pp;
map<int, int> vis;
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)
{
        map<int, int> viz;
        if (vecs.size() < 2)
        {
                return;
        }
        else if (vecs.size() == 2)
        {
                if (p[vecs[0]][vecs[1]] != 1)
                        bad = 1;
                answer[vecs[0]][vecs[1]] = answer[vecs[1]][vecs[0]] = 1;
                return;
        }
        vector<vector<int>> lines;
        int sz = (int)vecs.size();

        for (int i = 0; i < sz; ++i)
        {
                int v = vecs[i];
                if (viz[v]++)
                        continue;
                lines.push_back({v});
                for (int j = 0; j < sz; ++j)
                {
                        if (i == j || viz[vecs[j]])
                        {
                                continue;
                        }
                        if (p[v][vecs[j]] == 1)
                        {
                                viz[vecs[j]] = 1;
                                lines.back().push_back(vecs[j]);
                        }
                }
                for (int j = 0; j < (int) lines.size() ; ++j)
                {
                        for (auto u : lines.back())
                        {
                                for (auto k : lines[j])
                                {
                                        if (p[u][k] != 2)
                                                bad = 1;
                                }
                        }
                }
        }

        if (lines.size() == 2)
        {
                bad = 1;
        }
        for (int i = 0; i < (int)lines.size(); ++i)
        {
                int j = (i + 1) % (int)lines.size();
                int x = lines[i][0], y = lines[j][0];
                if (x != y)
                        answer[vecs[x]][vecs[y]] = answer[vecs[y]][vecs[x]] = 1;
                for (int k = 1; k < (int)lines[i].size(); ++k)
                {
                        int x = lines[i][k - 1], y = lines[i][k];
                        answer[vecs[x]][vecs[y]] = 1;
                        answer[vecs[y]][vecs[x]] = 1;
                }
        }
}

void clear()
{
        p.clear();
        answer.clear();
        vis.clear();
        bad = 0;
}

int vix[1001];
int root;

void dfs(int x)
{
        vix[x] = 1;
        if (x != root)
                p[root][x]--;
        for (int j = 0; j < nn; ++j)
        {
                if (x != j && pp[x][j] && !vix[j])
                {
                        dfs(j);
                }
        }
        vis[x] = 0;
}

bool check()
{
        pp = p;
        for (int i = 0; i < nn; ++i)
        {
                memset(vix, 0, sizeof vix);
                root = i;
                dfs(i);
        }
        for (int i = 0; i < nn; ++i)
        {
                for (int j = 0; j < nn; ++j)
                {
                        //cout<< p[i][j] <<" " ;
                        if (i == j)
                                continue;
                        if (p[i][j])
                                return 0;
                }
                //cout<<"...\n" ;
        }
        return 1;
}

int construct(std::vector<std::vector<int>> P)
{
        clear();
        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;
}

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