Submission #832653

#	Time	Username	Problem	Language	Result	Execution time	Memory
832653		finn__	Toy Train (IOI17_train)	C++17	100 / 100	282 ms	1324 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>> rg(n);
    vector<int> degree(n);
    for (size_t i = 0; i < m; ++i)
        rg[v[i]].push_back(u[i]), degree[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] == degree[v])
                    {
                        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;
                for (auto const &v : rg[i])
                    degree[v]--;
            }
    }

    return w;
}

Compilation message (stderr)

train.cpp: In function 'std::vector<int> who_wins(std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>)':
train.cpp:49:27: warning: comparison of integer expressions of different signedness: 'int' and 'const size_t' {aka 'const long unsigned int'} [-Wsign-compare]
   49 |         for (int i = 0; i < n; ++i)
      |                         ~~^~~
train.cpp:54: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]
   54 |         if (count(reaches_charge.begin(), reaches_charge.end(), 1) == l)
      |             ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~
train.cpp:56:31: warning: comparison of integer expressions of different signedness: 'int' and 'const size_t' {aka 'const long unsigned int'} [-Wsign-compare]
   56 |             for (int i = 0; i < n; ++i)
      |                             ~~^~~
train.cpp:63:27: warning: comparison of integer expressions of different signedness: 'int' and 'const size_t' {aka 'const long unsigned int'} [-Wsign-compare]
   63 |         for (int i = 0; i < n; ++i)
      |                         ~~^~~
train.cpp:67:27: warning: comparison of integer expressions of different signedness: 'int' and 'const size_t' {aka 'const long unsigned int'} [-Wsign-compare]
   67 |         for (int i = 0; i < n; ++i)
      |                         ~~^~~

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