Submission #160368

#	Time	Username	Problem	Language	Result	Execution time	Memory
160368		rama_pang	Toy Train (IOI17_train)	C++14	100 / 100	877 ms	1912 KiB

train

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

const int AREZOU = 1;
const int BORZOU = 0;

const int CHARGING_STATION = 1;

const int CHARGING_SET = 1;
const int NON_CHARGING_SET = 0;

const int VISITED = 1;
const int UNVISITED = 0;

int N, M;
vector<int> station, owner;
vector<vector<int>> G, G_inverse;

vector<int> in_degree;
vector<int> visited;
vector<int> charging_set;
vector<int> new_charging_set;

void initialize_charging_set() {
    visited.assign(N, UNVISITED);
    in_degree.assign(N, 0);
    charging_set.assign(N, NON_CHARGING_SET);

    queue<int> q;
    for (int i = 0; i < N; i++) 
        if (station[i] == CHARGING_STATION && new_charging_set[i] == CHARGING_SET) 
            q.push(i), visited[i] = VISITED;
    
    while (!q.empty()) {
        int u = q.front(); q.pop();
        charging_set[u] = CHARGING_SET;
        for (auto v : G_inverse[u]) {
            if (visited[v] == VISITED) continue;

            switch (owner[v]) {
            case AREZOU:
                if (visited[v] == UNVISITED) {  
                    visited[v] = VISITED;
                    q.push(v);
                }
                break;
            case BORZOU:
                in_degree[v]++;
                if (in_degree[v] == G[v].size() && visited[v] == UNVISITED) {
                    visited[v] = VISITED;
                    q.push(v);
                }
                break;
            }
        }
    }

}

vector<int> who_wins(vector<int> owner_, vector<int> charge_, vector<int> u_, vector<int> v_) {
	owner = owner_, station = charge_;
    N = owner.size(), M = u_.size();
    G.resize(N), G_inverse.resize(N);
    new_charging_set.resize(N, CHARGING_SET);

    for (int i = 0; i < M; i++) {
        G[u_[i]].push_back(v_[i]);
        G_inverse[v_[i]].push_back(u_[i]);
    }

    while (charging_set != new_charging_set) {
        initialize_charging_set();

        for (int i = 0; i < N; i++) {
            switch (owner[i]) {
            case AREZOU:
                new_charging_set[i] = NON_CHARGING_SET;
                for (auto v : G[i]) 
                    if (charging_set[v] == CHARGING_SET) 
                        new_charging_set[i] = CHARGING_SET;
                    
                break;
            
            case BORZOU:
                new_charging_set[i] = CHARGING_SET;
                for (auto v : G[i]) 
                    if (charging_set[v] == NON_CHARGING_SET) 
                        new_charging_set[i] = NON_CHARGING_SET;
                    
                break;
            }
        }

    }

    vector<int> res(N);
    for (int i = 0; i < N; i++) res[i] = (charging_set[i] == CHARGING_SET);

    return res;
}

Compilation message (stderr)

train.cpp: In function 'void initialize_charging_set()':
train.cpp:50:34: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
                 if (in_degree[v] == G[v].size() && visited[v] == UNVISITED) {

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