Submission #133414

#	Time	Username	Problem	Language	Result	Execution time	Memory
133414		icypiggy	Toy Train (IOI17_train)	C++14	15 / 100	2064 ms	191604 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!
bool whowin[n_max][n_max]; // position, then state. true = unknown, false = b wins
int deg[n_max][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]);
        for(int j=0; j<n_max; j++) {
            deg[u[i]][j]++;
        }
    }
}
vector<int> who_wins(vector<int> a,  vector<int> r, vector<int> u, vector<int> v) {
    init(u,v);
    int n = a.size();
    queue<pair<int,int>> bfs;
    for(int i=0; i<n; i++) {
        for(int j=0; j<=n; j++) {
            whowin[i][j] = true;
        }
        if(!r[i]) {
            whowin[i][0] = false;
            bfs.push(make_pair(i,0));
        }
    }
    while(!bfs.empty()) {
        pair<int,int> next = bfs.front();
        bfs.pop();
        if(r[next.first] && next.second==n) {
            for(int i: backward[next.first]) {
                if(a[i]) {
                    for(int j=0; j<=n; j++) {
                        deg[i][j]--;
                        if(deg[i][j]==0 && whowin[i][j]) {
                            whowin[i][j] = false;
                            bfs.push(make_pair(i,j));
                        }
                    }
                } else {
                    for(int j=0; j<=n; j++) {
                        if(whowin[i][j]) {
                            whowin[i][j] = false;
                            bfs.push(make_pair(i,j));
                        }
                    }
                }
            }
        } else if (next.second < n && r[next.first]==0) {
            for(int i: backward[next.first]) {
                int j = next.second + 1;
                if(a[i]) {
                    deg[i][j]--;
                    if(deg[i][j]==0 && whowin[i][j]) {
                        whowin[i][j] = false;
                        bfs.push(make_pair(i,j));
                    }
                } else {
                    if(whowin[i][j]) {
                        whowin[i][j] = false;
                        bfs.push(make_pair(i,j));
                    }
                }
            }
        }
    }
    vector<int> ans(n,0);
    for(int i=0; i<n; i++) {
        ans[i] = whowin[i][n];
    }
    return ans;
}

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++) {
                  ~^~~~~~~~~

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