oj.uz

Submission #832635

# Submission time Handle Problem Language Result Execution time Memory
832635 2023-08-21T12:50:36 Z finn__ Toy Train (IOI17_train) C++17
28 / 100
 138 ms 1652 KB 
#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

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.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 1108 KB Output is correct
2 Correct 4 ms 1080 KB Output is correct
3 Correct 4 ms 1108 KB Output is correct
4 Correct 4 ms 1080 KB Output is correct
5 Correct 4 ms 1108 KB Output is correct
6 Correct 4 ms 1108 KB Output is correct
7 Correct 4 ms 1084 KB Output is correct
8 Correct 5 ms 1076 KB Output is correct
9 Correct 4 ms 1108 KB Output is correct
10 Correct 3 ms 1108 KB Output is correct
11 Correct 3 ms 1108 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 0 ms 224 KB Output is correct
4 Correct 0 ms 216 KB Output is correct
5 Correct 0 ms 308 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Incorrect 0 ms 212 KB 3rd lines differ - on the 2nd token, expected: '0', found: '1'
9 Halted 0 ms 0 KB -

Subtask #3
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 48 ms 1620 KB Output is correct
2 Correct 96 ms 1644 KB Output is correct
3 Correct 138 ms 1652 KB Output is correct
4 Correct 6 ms 1620 KB Output is correct
5 Incorrect 7 ms 1592 KB 3rd lines differ - on the 11th token, expected: '0', found: '1'
6 Halted 0 ms 0 KB -

Subtask #4
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 1376 KB Output is correct
2 Correct 6 ms 1492 KB Output is correct
3 Correct 10 ms 1584 KB Output is correct
4 Correct 7 ms 1588 KB Output is correct
5 Correct 6 ms 1620 KB Output is correct
6 Correct 6 ms 1500 KB Output is correct
7 Correct 6 ms 1488 KB Output is correct
8 Correct 6 ms 1492 KB Output is correct
9 Correct 6 ms 1464 KB Output is correct
10 Correct 6 ms 1596 KB Output is correct
11 Correct 8 ms 1560 KB Output is correct
12 Correct 6 ms 1620 KB Output is correct
13 Correct 7 ms 1620 KB Output is correct
14 Correct 8 ms 1492 KB Output is correct

Subtask #5
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 1596 KB Output is correct
2 Correct 6 ms 1600 KB Output is correct
3 Correct 7 ms 1492 KB Output is correct
4 Correct 6 ms 1492 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 3 ms 1108 KB Output is correct
7 Correct 4 ms 980 KB Output is correct
8 Correct 4 ms 980 KB Output is correct
9 Correct 4 ms 980 KB Output is correct
10 Correct 1 ms 468 KB Output is correct
11 Correct 6 ms 928 KB Output is correct

Subtask #6
0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 1108 KB Output is correct
2 Correct 4 ms 1080 KB Output is correct
3 Correct 4 ms 1108 KB Output is correct
4 Correct 4 ms 1080 KB Output is correct
5 Correct 4 ms 1108 KB Output is correct
6 Correct 4 ms 1108 KB Output is correct
7 Correct 4 ms 1084 KB Output is correct
8 Correct 5 ms 1076 KB Output is correct
9 Correct 4 ms 1108 KB Output is correct
10 Correct 3 ms 1108 KB Output is correct
11 Correct 3 ms 1108 KB Output is correct
12 Correct 0 ms 212 KB Output is correct
13 Correct 1 ms 212 KB Output is correct
14 Correct 0 ms 224 KB Output is correct
15 Correct 0 ms 216 KB Output is correct
16 Correct 0 ms 308 KB Output is correct
17 Correct 1 ms 212 KB Output is correct
18 Correct 0 ms 212 KB Output is correct
19 Incorrect 0 ms 212 KB 3rd lines differ - on the 2nd token, expected: '0', found: '1'
20 Halted 0 ms 0 KB -