제출 #868214

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
868214		borisAngelov	도서관 (JOI18_library)	C++17	100 / 100	97 ms	1836 KiB

library

#include "library.h"
#include <bits/stdc++.h>

using namespace std;

const int maxn = 1005;

int n;

vector<int> g[maxn];

bool visited[maxn];

struct DSU
{
    int par[maxn];
    vector<int> components[maxn];

    void build(int n)
    {
        for (int i = 1; i <= n; ++i)
        {
            par[i] = i;
            components[i].push_back(i);
        }
    }

    int root(int node)
    {
        if (node == par[node])
        {
            return node;
        }

        return par[node] = root(par[node]);
    }
};

DSU dsu;

int divideAndConquer1(int l, int r, const vector<int>& componentRoots, int node)
{
    if (l == r)
    {
        return componentRoots[l];
    }

    int mid = (l + r) / 2;

    vector<int> leftNodes;

    for (int i = l; i <= mid; ++i)
    {
        for (int j = 0; j < dsu.components[componentRoots[i]].size(); ++j)
        {
            leftNodes.push_back(dsu.components[componentRoots[i]][j]);
        }
    }

    vector<int> takenBooks(n, false);

    for (int i = 0; i < leftNodes.size(); ++i)
    {
        takenBooks[leftNodes[i] - 1] = true;
    }

    takenBooks[node - 1] = true;

    int result = Query(takenBooks);

    if (result == mid - l + 1)
    {
        return divideAndConquer1(l, mid, componentRoots, node);
    }
    else
    {
        return divideAndConquer1(mid + 1, r, componentRoots, node);
    }
}

pair<int, int> divideAndConquer2(int l, int r, const vector<int>& componentRoots, int node)
{
    //cout << "now " << l << " to " << r << endl;

    int mid = (l + r) / 2;

    vector<int> leftNodes;

    for (int i = l; i <= mid; ++i)
    {
        for (int j = 0; j < dsu.components[componentRoots[i]].size(); ++j)
        {
            leftNodes.push_back(dsu.components[componentRoots[i]][j]);
        }
    }

    vector<int> takenBooks(n, false);

    for (int i = 0; i < leftNodes.size(); ++i)
    {
        //cout << "adding " << leftNodes[i] << endl;
        takenBooks[leftNodes[i] - 1] = true;
    }

    //cout << "adding " << node << endl;
    takenBooks[node - 1] = true;

    int result = Query(takenBooks);
    //cout << "result = " << result << " :: " << l << " and " << mid << " -> " << mid - l + 1 << endl;

    if (result == (mid - l + 1) - 1)
    {
        return divideAndConquer2(l, mid, componentRoots, node);
    }
    else if (result == (mid - l + 1) + 1)
    {
        return divideAndConquer2(mid + 1, r, componentRoots, node);
    }
    else
    {
        //cout << "here" << endl;
        return make_pair(divideAndConquer1(l, mid, componentRoots, node), divideAndConquer1(mid + 1, r, componentRoots, node));
    }
}

void Solve(int N)
{
    n = N;

    dsu.build(n);

    for (int i = 2; i <= n; ++i)
    {
        vector<int> componentRoots;

        for (int j = 1; j <= i - 1; ++j)
        {
            if (dsu.root(j) == j)
            {
                //cout << j << " it a root" << endl;
                componentRoots.push_back(j);
            }
        }

        vector<int> takenBooks(n, false);

        for (int j = 0; j < componentRoots.size(); ++j)
        {
            for (int k = 0; k < dsu.components[componentRoots[j]].size(); ++k)
            {
                takenBooks[dsu.components[componentRoots[j]][k] - 1] = true;
            }
        }

        takenBooks[i - 1] = true;

        int componentsWith = Query(takenBooks);
        int componentsWithout = componentRoots.size();

        //cout << "on " << i << " :: " << componentsWith << " and " << componentsWithout << endl;

        if (componentsWith == componentsWithout)
        {
            int whichComponentRoot = divideAndConquer1(0, componentRoots.size() - 1, componentRoots, i);

            int firstNode = -1;
            int secondNode = -1;

            for (int j = 0; j < dsu.components[whichComponentRoot].size(); ++j)
            {
                int node = dsu.components[whichComponentRoot][j];

                if (g[node].size() <= 1)
                {
                    if (firstNode == -1)
                    {
                        firstNode = node;
                    }
                    else
                    {
                        secondNode = node;
                    }
                }
            }

            vector<int> currentQuery(n, false);

            currentQuery[i - 1] = true;
            currentQuery[firstNode - 1] = true;

            if (Query(currentQuery) == 1)
            {
                //cout << "connect " << i << " and " << firstNode << endl;

                // connect i and first node
                g[firstNode].push_back(i);
                g[i].push_back(firstNode);

                dsu.components[whichComponentRoot].push_back(i);
                dsu.par[i] = whichComponentRoot;
            }
            else
            {
                //cout << "connect " << i << " and " << secondNode << endl;

                // connect i and second node
                g[secondNode].push_back(i);
                g[i].push_back(secondNode);

                dsu.components[whichComponentRoot].push_back(i);
                dsu.par[i] = whichComponentRoot;
            }
        }
        else if (componentsWith == componentsWithout - 1)
        {
            //cout << "before divide and conquer " << endl;
            pair<int, int> whichComponentRoots = divideAndConquer2(0, componentRoots.size() - 1, componentRoots, i);
            //cout << "after divide and conquer" << endl;

            int firstNode = -1;
            int secondNode = -1;

            for (int j = 0; j < dsu.components[whichComponentRoots.first].size(); ++j)
            {
                int node = dsu.components[whichComponentRoots.first][j];

                if (g[node].size() <= 1)
                {
                    if (firstNode == -1)
                    {
                        firstNode = node;
                    }
                    else
                    {
                        secondNode = node;
                    }
                }
            }

            vector<int> currentQuery(n, false);

            currentQuery[i - 1] = true;
            currentQuery[firstNode - 1] = true;

            if (Query(currentQuery) == 1)
            {
                //cout << "connect " << i << " and " << firstNode << endl;

                // connect i and first node
                g[firstNode].push_back(i);
                g[i].push_back(firstNode);

                dsu.components[whichComponentRoots.first].push_back(i);
                dsu.par[i] = whichComponentRoots.first;
            }
            else
            {
                //cout << "connect " << i << " and " << secondNode << endl;

                // connect i and second node
                g[secondNode].push_back(i);
                g[i].push_back(secondNode);

                dsu.components[whichComponentRoots.first].push_back(i);
                dsu.par[i] = whichComponentRoots.first;
            }

            currentQuery[i - 1] = false;
            currentQuery[firstNode - 1] = false;

            firstNode = -1;
            secondNode = -1;

            for (int j = 0; j < dsu.components[whichComponentRoots.second].size(); ++j)
            {
                int node = dsu.components[whichComponentRoots.second][j];

                if (g[node].size() <= 1)
                {
                    if (firstNode == -1)
                    {
                        firstNode = node;
                    }
                    else
                    {
                        secondNode = node;
                    }
                }
            }

            currentQuery[i - 1] = true;
            currentQuery[firstNode - 1] = true;

            if (Query(currentQuery) == 1)
            {
                //cout << "connect " << i << " and " << firstNode << endl;

                // connect i and first node
                g[firstNode].push_back(i);
                g[i].push_back(firstNode);

                dsu.components[whichComponentRoots.second].push_back(i);
                dsu.par[i] = whichComponentRoots.second;
            }
            else
            {
                //cout << "connect " << i << " and " << secondNode << endl;

                // connect i and second node
                g[secondNode].push_back(i);
                g[i].push_back(secondNode);

                dsu.components[whichComponentRoots.second].push_back(i);
                dsu.par[i] = whichComponentRoots.second;
            }

            dsu.par[whichComponentRoots.second] = dsu.par[whichComponentRoots.first];

            for (int j = 0; j < dsu.components[whichComponentRoots.second].size(); ++j)
            {
                dsu.components[whichComponentRoots.first].push_back(dsu.components[whichComponentRoots.second][j]);
            }
        }
    }

    int currentNode = -1;

    for (int i = 1; i <= n; ++i)
    {
        if (g[i].size() <= 1)
        {
            currentNode = i;
            break;
        }
    }

    vector<int> ans;

    while (ans.size() < n)
    {
        //cout << "on " << currentNode << endl;
        ans.push_back(currentNode);
        visited[currentNode] = true;

        for (int i = 0; i < g[currentNode].size(); ++i)
        {
            int nxt = g[currentNode][i];

            if (visited[nxt] == false)
            {
                currentNode = nxt;
                break;
            }
        }
    }

    Answer(ans);
}

컴파일 시 표준 에러 (stderr) 메시지

library.cpp: In function 'int divideAndConquer1(int, int, const std::vector<int>&, int)':
library.cpp:54:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   54 |         for (int j = 0; j < dsu.components[componentRoots[i]].size(); ++j)
      |                         ~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
library.cpp:62:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   62 |     for (int i = 0; i < leftNodes.size(); ++i)
      |                     ~~^~~~~~~~~~~~~~~~~~
library.cpp: In function 'std::pair<int, int> divideAndConquer2(int, int, const std::vector<int>&, int)':
library.cpp:91:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   91 |         for (int j = 0; j < dsu.components[componentRoots[i]].size(); ++j)
      |                         ~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
library.cpp:99:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   99 |     for (int i = 0; i < leftNodes.size(); ++i)
      |                     ~~^~~~~~~~~~~~~~~~~~
library.cpp: In function 'void Solve(int)':
library.cpp:147:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  147 |         for (int j = 0; j < componentRoots.size(); ++j)
      |                         ~~^~~~~~~~~~~~~~~~~~~~~~~
library.cpp:149:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  149 |             for (int k = 0; k < dsu.components[componentRoots[j]].size(); ++k)
      |                             ~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
library.cpp:169:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  169 |             for (int j = 0; j < dsu.components[whichComponentRoot].size(); ++j)
      |                             ~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
library.cpp:223:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  223 |             for (int j = 0; j < dsu.components[whichComponentRoots.first].size(); ++j)
      |                             ~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
library.cpp:274:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  274 |             for (int j = 0; j < dsu.components[whichComponentRoots.second].size(); ++j)
      |                             ~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
library.cpp:319:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  319 |             for (int j = 0; j < dsu.components[whichComponentRoots.second].size(); ++j)
      |                             ~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
library.cpp:339:23: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  339 |     while (ans.size() < n)
      |            ~~~~~~~~~~~^~~
library.cpp:345:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  345 |         for (int i = 0; i < g[currentNode].size(); ++i)
      |                         ~~^~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 19 / 19
• Subtask 2: 81 / 81