Submission #641883

#	Time	Username	Problem	Language	Result	Execution time	Memory
641883		piOOE	Toy Train (IOI17_train)	C++17	100 / 100	533 ms	1652 KiB

train

#include <bits/stdc++.h>
#include "train.h"

using namespace std;

constexpr int N = 5000;

vector<int> rev[N], g[N], a;
int n;

void bfs(vector<int> &used, int player) {
    vector<int> degree(n);
    queue<int> q;
    for (int i = 0; i < n; ++i) {
        if (used[i]) {
            q.push(i);
        }
    }

    while (!q.empty()) {
        int v = q.front();
        q.pop();
        for (int to: rev[v]) {
            if (!used[to] && (a[to] == player || ++degree[to] == g[to].size())) {
                used[to] = true;
                q.push(to);
            }
        }
    }
}

std::vector<int> who_wins(std::vector<int> a, std::vector<int> r, std::vector<int> A, std::vector<int> B) {
    ::a = a;
    n = a.size();
    for (int i = 0; i < A.size(); ++i) {
        g[A[i]].push_back(B[i]);
        rev[B[i]].push_back(A[i]);
    }
    bool found = true;
    while (found) {
        found = false;
        vector<int> used = r;
        bfs(used, 1);
        for (int &i: used) {
            i ^= 1;
        }
        bfs(used, 0);
        for (int i = 0; i < n; ++i) {
            if (r[i] == 1 && used[i]) {
                r[i] = 0;
                found = true;
            }
        }
    }
    vector<int> ans = r;
    bfs(ans, 1);
    return ans;
}

Compilation message (stderr)

train.cpp: In function 'void bfs(std::vector<int>&, int)':
train.cpp:24:63: 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]
   24 |             if (!used[to] && (a[to] == player || ++degree[to] == g[to].size())) {
      |                                                  ~~~~~~~~~~~~~^~~~~~~~~~~~~~~
train.cpp: In function 'std::vector<int> who_wins(std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>)':
train.cpp:35:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   35 |     for (int i = 0; i < A.size(); ++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