Submission #313577

#	Time	Username	Problem	Language	Result	Execution time	Memory
313577		mohamedsobhi777	슈퍼트리 잇기 (IOI20_supertrees)	C++14	0 / 100	290 ms	26104 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)
{
        map<int, int> viz;
        if (vecs.size() < 2)
        {
                return;
        }
        else if (vecs.size() == 2)
        {
                if (p[vecs[0]][vecs[1]] != 1)
                        bad = 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]);
                        }
                }
        }

        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;
                }
        }
}

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;
}

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