Submission #160350

#	Time	Username	Problem	Language	Result	Execution time	Memory
160350		rama_pang	Toy Train (IOI17_train)	C++14	0 / 100	631 ms	1684 KiB

train

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

const int AREZOU = 1;
const int BORZOU = 0;
const int UNDETERMINED = -1;
const int CHARGING_STATION = 1;
const int NORMAL_STATION = 0;

int N, M;
vector<int> charge, owner;
vector<vector<int>> G;

vector<int> winning;
vector<int> visited;
int VISITED = 0;

void BFS(int OWNER, int STATION) {
    queue<int> q;

    for (int i = 0; i < N; i++) if (charge[i] == STATION && owner[i] == OWNER) {
        for (auto v : G[i]) if (owner[v] == OWNER) q.push(v);

        bool WINNING = false;
        VISITED++;

        while (!q.empty()) {
            int u = q.front(); q.pop();
            if (u == i) {
                WINNING = true;
                break;
            }

            for (auto v : G[u]) if (owner[v] == OWNER && visited[v] != VISITED) {
                visited[v] = VISITED;
                q.push(v);
            }
        }

        if (WINNING) winning[i] = OWNER;
    }

    for (int i = 0; i < N; i++) if (charge[i] != STATION && owner[i] == OWNER) {
        bool WINNING = false;
        VISITED++;
        q.push(i);

        while (!q.empty()) {
            int u = q.front(); q.pop();
            if (winning[u] == OWNER) {
                WINNING = true;
                break;
            }

            for (auto v : G[u]) if (owner[v] == OWNER && visited[v] != VISITED) {
                visited[v] = VISITED;
                q.push(v);
            }
        }

        if (WINNING) winning[i] = OWNER;
    }

}

vector<int> who_wins(vector<int> owner_, vector<int> charge_, vector<int> u_, vector<int> v_) {
	owner = owner_, charge = charge_;
    N = owner.size(), M = u_.size();
    G.resize(N), visited.assign(N, VISITED), winning.assign(N, UNDETERMINED);

    for (int i = 0; i < M; i++) G[u_[i]].push_back(v_[i]);
    
    BFS(AREZOU, CHARGING_STATION);
    BFS(BORZOU, NORMAL_STATION);

    for (int n = 0; n < N; n++) {
        for (int i = 0; i < N; i++) {
            if (winning[i] != UNDETERMINED) continue;
            bool WINNING;
            if (owner[i] == AREZOU) WINNING = false;
            if (owner[i] == BORZOU) WINNING = true;
            for (auto v : G[i]) {
                if (owner[v] == owner[i] && winning[v] != UNDETERMINED) {
                    WINNING = !WINNING;
                    break;
                }
            }
            winning[i] = WINNING;
        }
    }

    vector<int> res(owner.size());
    for (int i = 0; i < N; i++) res[i] = winning[i];

    return res;
}

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:85:29: warning: 'WINNING' may be used uninitialized in this function [-Wmaybe-uninitialized]
                     WINNING = !WINNING;
                     ~~~~~~~~^~~~~~~~~~

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