Submission #133394

#	Time	Username	Problem	Language	Result	Execution time	Memory
133394		icypiggy	Toy Train (IOI17_train)	C++14	12 / 100	380 ms	262144 KiB

train

#include <iostream>
#include <vector>
#include <bitset>
#include <queue>
#include <string.h>

using namespace std;
const int n_max = 6000;
vector<int> backward[n_max]; // edges run in the reverse direction!
vector<int> adj[n_max];
int deg[n_max]; // this is the out degree
int first_time = true;
void init(vector<int> &u, vector<int> &v) {
    memset(deg, 0, sizeof(deg));
    for(int i=0; i<u.size(); i++) {
        backward[v[i]].push_back(u[i]);
        adj[u[i]].push_back(v[i]);
        deg[u[i]]++;
    }
}
vector<int> who_wins(vector<int> a,  vector<int> r, vector<int> u, vector<int> v) {
    if(first_time) {
        init(u,v);
        first_time = false;
    }
    vector<int> ans(a.size(), 0); // initially b always wins
    queue<int> bfs;
    for(int i=0; i<r.size(); i++) {
        if(r[i]) {
            bfs.push(i); // put in all the chargers
            ans[i] = 1;
        }
    }
    while(!bfs.empty()) {
        int next = bfs.front();
        bfs.pop();
        for(int i: backward[next]) {
            if(ans[i]==0) {
                if(a[i]) {
                    ans[i] = true;
                    bfs.push(i);
                } else {
                    deg[i]--;
                    if(deg[i]==0) {
                        ans[i] = true;
                        bfs.push(i);
                    }
                }
            }
        }
    }
    bool bad = false;
    for(int i=0; i<r.size(); i++) {
        if(r[i]) {
            if(a[i]) {
                r[i] = false;
                // you win as long as there exists an outgoing win
                for(int j: adj[i]) {
                    if(ans[j]) {
                        r[i] = true;
                    }
                }
            } else {
                for(int j: adj[i]) {
                    if(ans[j]==0) {
                        r[i] = false;
                    }
                }
            }
            if(r[i]==false) {
                //cout << "charger " << i << " is bad\n";
                bad = true;
            }
        }
    }
    return (bad ? who_wins(a,r,u,v) : ans);
}

Compilation message (stderr)

train.cpp: In function 'void init(std::vector<int>&, std::vector<int>&)':
train.cpp:15:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0; i<u.size(); i++) {
                  ~^~~~~~~~~
train.cpp: In function 'std::vector<int> who_wins(std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>)':
train.cpp:28:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0; i<r.size(); i++) {
                  ~^~~~~~~~~
train.cpp:53:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0; i<r.size(); i++) {
                  ~^~~~~~~~~

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