Submission #133397

#	Time	Username	Problem	Language	Result	Execution time	Memory
133397		icypiggy	Toy Train (IOI17_train)	C++14	100 / 100	643 ms	1840 KiB

train

#include <iostream>
#include <vector>
#include <bitset>
#include <queue>
#include <string.h>
#include <assert.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

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) {
    init(u,v);
    bool bad = true;
    while(bad) {
        bad = 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);
                        }
                    }
                }
            }
        }
        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;
                }
            }
        }
        if(!bad) {
            return ans;
        }
        memset(deg, 0, sizeof(deg));
        for(int i=0; i<u.size(); i++) {
            deg[u[i]]++;
        }
    }
    vector<int> aaa;
    assert(false);
    return aaa;
}

Compilation message (stderr)

train.cpp: In function 'void init(std::vector<int>&, std::vector<int>&)':
train.cpp:16: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:29:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int i=0; i<r.size(); i++) {
                      ~^~~~~~~~~
train.cpp:53:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int i=0; i<r.size(); i++) {
                      ~^~~~~~~~~
train.cpp:80:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int i=0; i<u.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