oj.uz

Submission #561791

# Submission time Handle Problem Language Result Execution time Memory
561791 2022-05-13T14:09:51 Z timreizin Meetings (JOI19_meetings) C++17
0 / 100
 2000 ms 262144 KB 
#include "meetings.h"
#include <random>
#include <vector>
#include <set>
#include <numeric>
#include <cassert>

using namespace std;

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

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] = false;
                        --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())
    {
        bool was = false;
        for (int u : adj[v])
        {
            if (path.find(u) != path.end())
            {
                path.erase(u);
                v = u;
                was = true;
            }
        }
        assert(was);
    }
    return v;
    //findPath
}

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:33:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   33 |             for (int i = 0; i < vertices.size(); ++i)
      |                             ~~^~~~~~~~~~~~~~~~~
meetings.cpp:46:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   46 |             for (int i = 0; i < vertices.size(); ++i)
      |                             ~~^~~~~~~~~~~~~~~~~

Subtask #1
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 336 KB Output is correct
2 Correct 1 ms 336 KB Output is correct
3 Correct 1 ms 336 KB Output is correct
4 Correct 1 ms 336 KB Output is correct
5 Correct 0 ms 336 KB Output is correct
6 Correct 0 ms 336 KB Output is correct
7 Correct 0 ms 336 KB Output is correct
8 Runtime error 126 ms 262144 KB Execution killed with signal 9
9 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 336 KB Output is correct
2 Correct 1 ms 336 KB Output is correct
3 Correct 1 ms 336 KB Output is correct
4 Correct 1 ms 336 KB Output is correct
5 Correct 0 ms 336 KB Output is correct
6 Correct 0 ms 336 KB Output is correct
7 Correct 0 ms 336 KB Output is correct
8 Runtime error 126 ms 262144 KB Execution killed with signal 9
9 Halted 0 ms 0 KB -

Subtask #3
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 336 KB Output is correct
2 Correct 1 ms 336 KB Output is correct
3 Correct 1 ms 336 KB Output is correct
4 Correct 1 ms 336 KB Output is correct
5 Correct 0 ms 336 KB Output is correct
6 Correct 0 ms 336 KB Output is correct
7 Correct 0 ms 336 KB Output is correct
8 Runtime error 126 ms 262144 KB Execution killed with signal 9
9 Halted 0 ms 0 KB -

Subtask #4
0 / 71.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3027 ms 1640 KB Time limit exceeded
2 Halted 0 ms 0 KB -