Submission #561798

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
561798	2022-05-13T14:22:26 Z	timreizin	Meetings (JOI19_meetings)	C++17	Compilation error	0 ms	0 KB

meetings

#pragma GCC optimize("Ofast,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,popcnt,lzcnt")

#include "meetings.h"
#include <random>
#include <vector>
#include <set>
#include <numeric>
#include <cassert>

using namespace std;

vector<vector<int>> adj;
mt19937 gen(random_device());

int find(vector<int> vertices, int pivot, set<int> path)
{
    if (vertices.size() == 1) return vertices.front();
    if (vertices.size() == 2)
    {
        //do
        adj[vertices.front()].push_back(vertices.back());
        adj[vertices.back()].push_back(vertices.front());
    }
    else
    {
        vector<bool> used(vertices.size());
        int left = vertices.size();
        int pivot = uniform_int_distribution<>(0, left - 1)(gen);
        used[pivot] = true;
        --left;
        pivot = vertices[pivot];
        while (left)
        {
            int p = uniform_int_distribution<>(1, left)(gen);
            for (int i = 0; i < vertices.size(); ++i)
            {
                p -= !used[i];
                if (!p)
                {
                    --left;
                    used[i] = true;
                    p = vertices[i];
                    break;
                }
            }
            vector<int> next{p};
            set<int> path;
            for (int i = 0; i < vertices.size(); ++i)
            {
                if (!used[i])
                {
                    int r = Query(vertices[i], p, pivot);
                    if (r != pivot)
                    {
                        used[i] = true;
                        --left;
                        next.push_back(vertices[i]);
                        if (r == vertices[i]) path.insert(r);
                    }
                }
            }
            int e = find(next, p, path);
            adj[pivot].push_back(e);
            adj[e].push_back(pivot);
        }
    }
    int v = pivot;
    while (!path.empty())
    {
        for (int u : adj[v])
        {
            if (path.find(u) != path.end())
            {
                path.erase(u);
                v = u;
            }
        }
    }
    return v;
}

void Solve(int n)
{
    adj.resize(n);
    set<int> path;
    vector<int> vertices(n);
    iota(vertices.begin(), vertices.end(), 0);
    find(vertices, 0, path);
    for (int i = 0; i < n; ++i)
    {
        for (int u : adj[i])
        {
            if (i < u) Bridge(i, u);
        }
    }
}

Compilation message

meetings.cpp: In function 'int find(std::vector<int>, int, std::set<int>)':
meetings.cpp:36:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   36 |             for (int i = 0; i < vertices.size(); ++i)
      |                             ~~^~~~~~~~~~~~~~~~~
meetings.cpp:49:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   49 |             for (int i = 0; i < vertices.size(); ++i)
      |                             ~~^~~~~~~~~~~~~~~~~
In file included from /usr/include/c++/10/bits/random.h:35,
                 from /usr/include/c++/10/random:49,
                 from meetings.cpp:5:
/usr/include/c++/10/bits/uniform_int_dist.h: In instantiation of 'std::uniform_int_distribution<_IntType>::result_type std::uniform_int_distribution<_IntType>::operator()(_UniformRandomNumberGenerator&, const std::uniform_int_distribution<_IntType>::param_type&) [with _UniformRandomNumberGenerator = std::mersenne_twister_engine<long unsigned int, 32, 624, 397, 31, 2567483615, 11, 4294967295, 7, 2636928640, 15, 4022730752, 18, 1812433253>(std::random_device (*)()); _IntType = int; std::uniform_int_distribution<_IntType>::result_type = int]':
/usr/include/c++/10/bits/uniform_int_dist.h:189:34:   required from 'std::uniform_int_distribution<_IntType>::result_type std::uniform_int_distribution<_IntType>::operator()(_UniformRandomNumberGenerator&) [with _UniformRandomNumberGenerator = std::mersenne_twister_engine<long unsigned int, 32, 624, 397, 31, 2567483615, 11, 4294967295, 7, 2636928640, 15, 4022730752, 18, 1812433253>(std::random_device (*)()); _IntType = int; std::uniform_int_distribution<_IntType>::result_type = int]'
meetings.cpp:29:64:   required from here
/usr/include/c++/10/bits/uniform_int_dist.h:246:4: error: 'std::mersenne_twister_engine<long unsigned int, 32, 624, 397, 31, 2567483615, 11, 4294967295, 7, 2636928640, 15, 4022730752, 18, 1812433253>(std::random_device (*)())' is not a class, struct, or union type
  246 |    _Gresult_type;
      |    ^~~~~~~~~~~~~
/usr/include/c++/10/bits/uniform_int_dist.h:249:4: error: 'std::mersenne_twister_engine<long unsigned int, 32, 624, 397, 31, 2567483615, 11, 4294967295, 7, 2636928640, 15, 4022730752, 18, 1812433253>(std::random_device (*)())' is not a class, struct, or union type
  249 |    __uctype;
      |    ^~~~~~~~
/usr/include/c++/10/bits/uniform_int_dist.h:266:31: error: too few arguments to function
  266 |        __ret = __uctype(__urng()) - __urngmin;
      |                         ~~~~~~^~
/usr/include/c++/10/bits/uniform_int_dist.h:293:35: error: too few arguments to function
  293 |   __ret = __tmp + (__uctype(__urng()) - __urngmin);
      |                             ~~~~~~^~
/usr/include/c++/10/bits/uniform_int_dist.h:298:27: error: too few arguments to function
  298 |    __ret = __uctype(__urng()) - __urngmin;
      |                     ~~~~~~^~