Submission #134041

#	Time	Username	Problem	Language	Result	Execution time	Memory
134041		icypiggy	Toy Train (IOI17_train)	C++14	5 / 100	2091 ms	191924 KiB

train

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

using namespace std;
const int n_max = 6000;
vector<int> backward[n_max]; // edges run in the reverse direction!
vector<int> adj[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
int n;

void init(vector<int> &u, vector<int> &v) {
    memset(deg, 0, sizeof(deg));
    for(int i=0; i<n_max; i++) {
        backward[i].clear();
        adj[i].clear();
    }
    for(int i=0; i<u.size(); i++) {
        backward[v[i]].push_back(u[i]);
        adj[u[i]].push_back(v[i]);
        for(int j=0; j<n_max; j++) {
            deg[u[i]][j]++;
        }
    }
}
stack<int> st;
int cmp_count = 0;
int component[n_max];
bitset<n_max> visited;
void dfs1(int x, vector<int> &a) {
    if(!visited[x]) {
        visited[x] = true;
        for(int i: adj[x]) {
            if(a[x] == a[i] && !visited[i]) {
                dfs1(i, a);
            }
        }
        st.push(x);
        //cout << "pushed: " << x << "\n";
    }
}
void dfs2(int x, vector<int> &a) {
    component[x] = cmp_count;
    if(visited[x]) {
        visited[x] = false;
        for(int i: backward[x]) {
            if(a[x]==a[i] && visited[i]) {
                dfs2(i, a);
            }
        }
    }
}
void scc(vector<int> &a) {
    for(int i=0; i<n; i++) {
        if(!visited[i]) {
            //cout << "seed " << i << "\n";
            dfs1(i, a);
        }
    }
    while(!st.empty()) {
        int next = st.top();
        st.pop();
        if(visited[next]) {
            dfs2(next, a);
            cmp_count++;
        }
    }
}
vector<int> who_wins(vector<int> a,  vector<int> r, vector<int> u, vector<int> v) {
    init(u,v);
    n = a.size();
    int n_prev = a.size();
    scc(a);
    for(int i=0; i<u.size(); i++) {
        u[i] = component[u[i]];
        v[i] = component[v[i]];
    }


    vector<int> a2(cmp_count, 0);
    vector<int> r2(cmp_count, 0);
    for(int i=0; i<n; i++) {
        a2[component[i]] = a[i];
        r2[component[i]] |= r[i];
    }
    a = a2;
    r = r2;
    init(u,v);
    //n = cmp_count;

    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_prev,0);
    for(int i=0; i<n_prev; i++) {
        //cout << i << " " << component[i] << "\n";
        ans[i] = whowin[component[i]][n];
    }
    return ans;
}

Compilation message (stderr)

train.cpp: In function 'void init(std::vector<int>&, std::vector<int>&)':
train.cpp:23: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:79: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: 0 / 10
• Subtask 3: 0 / 11
• Subtask 4: 0 / 11
• Subtask 5: 0 / 12
• Subtask 6: 0 / 51