Submission #261980

#	Time	Username	Problem	Language	Result	Execution time	Memory
261980		Alexa2001	Toy Train (IOI17_train)	C++17	100 / 100	376 ms	34428 KiB

train

#include "train.h"
#include <bits/stdc++.h>

using namespace std;

const int Nmax = 5005;

int n, m;
int cnt[Nmax], Sz[Nmax];
vector<int> ans, a, r, v, go[Nmax];

bool reach[Nmax];


void solve()
{
    if(v.empty()) return;

    queue<int> q;

    for(auto node : v)
    {
        assert(Sz[node]);
        assert(a[node] != -1);

        if(r[node])
        {
            q.push(node);
            reach[node] = 1;
        }
        else reach[node] = 0;

        cnt[node] = 0;
    }

    while(q.size())
    {
        int node = q.front();
        q.pop();

        for(auto it : go[node])
            if(a[it] != -1)
            {
                ++cnt[it];
                if( !reach[it] && ((a[it] && cnt[it] == 1) || (!a[it] && cnt[it] == Sz[it])) )
                {
                    q.push(it);
                    reach[it] = 1;
                }
            }
    }

    int nr = 0;
    for(auto it : v)
        if(reach[it]) ++nr;

    if(nr == v.size()) /// toate sunt castigatoare
    {
        for(auto it : v)
            ans[it] = 1, a[it] = -1;
        return;
    }

    for(auto node : v)
    {
        if(!reach[node])
        {
            q.push(node);
            reach[node] = 1;
        }
        else reach[node] = 0;

        cnt[node] = 0;
    }

    while(q.size())
    {
        int node = q.front();
        q.pop();

        for(auto it : go[node])
            if(a[it] != -1)
            {
                ++cnt[it];
                if(!reach[it] && ((!a[it] && cnt[it] == 1) || (a[it] && cnt[it] == Sz[it]) ))
                {
                    q.push(it);
                    reach[it] = 1;
                }
            }
    }

    vector<int> vv;

    for(auto node : v)
        if(reach[node]) /// it este pierzator si il scot
        {
            for(auto it : go[node])
                --Sz[it];
            a[node] = -1;
        }
        else vv.push_back(node);

    swap(v, vv);

    solve();
}

vector<int> who_wins(vector<int> A, vector<int> R, vector<int> U, vector<int> V)
{
    r = R;
    a = A;
    n = a.size();
    m = U.size();

    v.resize(n);
    iota(v.begin(), v.end(), 0);

    int i;
    for(i=0; i<m; ++i)
        go[V[i]].push_back(U[i]), ++Sz[U[i]];

    ans.resize(n);

    solve();
    return ans;
}

Compilation message (stderr)

train.cpp: In function 'void solve()':
train.cpp:57:11: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     if(nr == v.size()) /// toate sunt castigatoare
        ~~~^~~~~~~~~~~

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