Submission #832635

#	Time	Username	Problem	Language	Result	Execution time	Memory
832635		finn__	Toy Train (IOI17_train)	C++17	28 / 100	138 ms	1652 KiB

train

#include "train.h"
#include <bits/stdc++.h>
using namespace std;

vector<int> who_wins(vector<int> a, vector<int> r, vector<int> u, vector<int> v)
{
    size_t const n = a.size(), m = u.size();

    vector<vector<int>> g(n), rg(n);
    for (size_t i = 0; i < m; ++i)
        g[u[i]].push_back(v[i]), rg[v[i]].push_back(u[i]);
    vector<bool> deleted(n);

    auto reaching_set = [&](vector<int> const &s, bool who)
    {
        vector<bool> in_the_set(n);
        vector<int> degree_to_the_set(n);
        queue<int> q;
        for (int const &u : s)
            in_the_set[u] = 1, q.push(u);

        while (!q.empty())
        {
            auto const u = q.front();
            q.pop();

            for (auto const &v : rg[u])
                if (!deleted[v] && !in_the_set[v])
                {
                    if (a[v] != who)
                        degree_to_the_set[v]++;
                    if (a[v] == who || degree_to_the_set[v] == g[v].size())
                    {
                        in_the_set[v] = 1;
                        q.push(v);
                    }
                }
        }

        return in_the_set;
    };

    size_t l = n;
    vector<int> w(n);
    while (l)
    {
        vector<int> charge_stations;
        for (int i = 0; i < n; ++i)
            if (!deleted[i] && r[i])
                charge_stations.push_back(i);
        auto reaches_charge = reaching_set(charge_stations, 1);

        if (count(reaches_charge.begin(), reaches_charge.end(), 1) == l)
        {
            for (int i = 0; i < n; ++i)
                if (!deleted[i])
                    w[i] = 1;
            break;
        }

        vector<int> doesnt_reach_charge;
        for (int i = 0; i < n; ++i)
            if (!deleted[i] && !reaches_charge[i])
                doesnt_reach_charge.push_back(i);
        auto winning_for_b = reaching_set(doesnt_reach_charge, 0);
        for (int i = 0; i < n; ++i)
            if (winning_for_b[i])
                deleted[i] = 1, --l;
    }

    return w;
}

Compilation message (stderr)

train.cpp: In lambda function:
train.cpp:32:61: warning: comparison of integer expressions of different signedness: '__gnu_cxx::__alloc_traits<std::allocator<int>, int>::value_type' {aka 'int'} and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   32 |                     if (a[v] == who || degree_to_the_set[v] == g[v].size())
train.cpp: In function 'std::vector<int> who_wins(std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>)':
train.cpp:48:27: warning: comparison of integer expressions of different signedness: 'int' and 'const size_t' {aka 'const long unsigned int'} [-Wsign-compare]
   48 |         for (int i = 0; i < n; ++i)
      |                         ~~^~~
train.cpp:53:68: warning: comparison of integer expressions of different signedness: 'std::__iterator_traits<std::_Bit_iterator, void>::difference_type' {aka 'long int'} and 'size_t' {aka 'long unsigned int'} [-Wsign-compare]
   53 |         if (count(reaches_charge.begin(), reaches_charge.end(), 1) == l)
      |             ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~
train.cpp:55:31: warning: comparison of integer expressions of different signedness: 'int' and 'const size_t' {aka 'const long unsigned int'} [-Wsign-compare]
   55 |             for (int i = 0; i < n; ++i)
      |                             ~~^~~
train.cpp:62:27: warning: comparison of integer expressions of different signedness: 'int' and 'const size_t' {aka 'const long unsigned int'} [-Wsign-compare]
   62 |         for (int i = 0; i < n; ++i)
      |                         ~~^~~
train.cpp:66:27: warning: comparison of integer expressions of different signedness: 'int' and 'const size_t' {aka 'const long unsigned int'} [-Wsign-compare]
   66 |         for (int i = 0; i < n; ++i)
      |                         ~~^~~

• Subtask 1: 5 / 5
• Subtask 2: 0 / 10
• Subtask 3: 0 / 11
• Subtask 4: 11 / 11
• Subtask 5: 12 / 12
• Subtask 6: 0 / 51