Submission #269697

#	Time	Username	Problem	Language	Result	Execution time	Memory
269697		hamerin	Toy Train (IOI17_train)	C++17	100 / 100	1941 ms	1452 KiB

train

#include "train.h"

#include <bits/stdc++.h>

#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")

using namespace std;

using i64 = long long;
using d64 = long double;
using pi = pair<int, int>;
using pli = pair<i64, i64>;
using ti = tuple<int, int, int>;
using tli = tuple<i64, i64, i64>;

#define iterall(cont) cont.begin(), cont.end()
#define prec(n) setprecision(n) << fixed

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

    vector<vector<int>> invGraph(N);
    vector<int> outdeg(N);
    for (auto i = 0; i < M; i++) {
        invGraph[v[i]].emplace_back(u[i]);
        outdeg[u[i]]++;
    }

    vector<bool> notBWin(N);

    // 몰라 대충 N번 돌리면 되겠지
    for (auto __loop = 0; __loop < N; __loop++) {
        vector<int> curoutdeg(N);
        queue<int> que;

        fill(iterall(notBWin), false);
        for (auto i = 0; i < N; i++)
            if (r[i]) que.emplace(i), notBWin[i] = true;
        while (!que.empty()) {
            auto cur = que.front();
            que.pop();

            for (auto el : invGraph[cur]) {
                if (notBWin[el]) continue;

                curoutdeg[el]++;
                if (a[el] || (!a[el] && curoutdeg[el] == outdeg[el])) {
                    notBWin[el] = true;
                    que.emplace(el);
                }
            }
        }

        fill(iterall(curoutdeg), 0);
        for (auto i = 0; i < N; i++)
            if (!notBWin[i]) que.emplace(i);
        while (!que.empty()) {
            auto cur = que.front();
            que.pop();

            for (auto el : invGraph[cur]) {
                if (!notBWin[el]) continue;

                curoutdeg[el]++;
                if (!a[el] || (a[el] && curoutdeg[el] == outdeg[el])) {
                    notBWin[el] = false;
                    que.emplace(el);
                }
            }
        }

		for(int i=0;i<N;i++) if(!notBWin[i] && r[i]) r[i] = false;
    }

	vector<int> ret;
	copy(iterall(notBWin), back_inserter(ret));

    return ret;
}

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:27:24: warning: comparison of integer expressions of different signedness: 'int' and 'const size_t' {aka 'const long unsigned int'} [-Wsign-compare]
   27 |     for (auto i = 0; i < M; i++) {
      |                      ~~^~~
train.cpp:35:34: warning: comparison of integer expressions of different signedness: 'int' and 'const size_t' {aka 'const long unsigned int'} [-Wsign-compare]
   35 |     for (auto __loop = 0; __loop < N; __loop++) {
      |                           ~~~~~~~^~~
train.cpp:40:28: warning: comparison of integer expressions of different signedness: 'int' and 'const size_t' {aka 'const long unsigned int'} [-Wsign-compare]
   40 |         for (auto i = 0; i < N; i++)
      |                          ~~^~~
train.cpp:58:28: warning: comparison of integer expressions of different signedness: 'int' and 'const size_t' {aka 'const long unsigned int'} [-Wsign-compare]
   58 |         for (auto i = 0; i < N; i++)
      |                          ~~^~~
train.cpp:75:16: warning: comparison of integer expressions of different signedness: 'int' and 'const size_t' {aka 'const long unsigned int'} [-Wsign-compare]
   75 |   for(int i=0;i<N;i++) if(!notBWin[i] && r[i]) r[i] = false;
      |               ~^~

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