Submission #221800

#	Time	Username	Problem	Language	Result	Execution time	Memory
221800		patrikpavic2	Toy Train (IOI17_train)	C++17	100 / 100	494 ms	1792 KiB

train

/**
* user:  ppavic
* fname: Patrik
* lname: Pavić
* task:  train
* score: 100.0
* date:  2019-06-12 09:27:16.425930
*/
#include "train.h"
#include <vector>
#include <cstring>
#include <queue>

#define PB push_back

using namespace std;

typedef vector < int > vi;

const int N = 5055;

int spas[N]; /// HDZ
int smrt[N]; /// SDP
int n;

vi v[N], r[N];
int cnt[N], izb[N];
queue < int > Q;

vi who_wins(vi a, vi rr, vi uu, vi vv) {
    n = a.size();
    for(int i  = 0;i < (int)vv.size();i++){
        v[uu[i]].PB(vv[i]);
        r[vv[i]].PB(uu[i]);
    }
    int kol = 0;
    for(;;kol++){
        memset(spas, 0, sizeof(spas));
        memset(smrt, 0, sizeof(smrt));
        memset(cnt, 0, sizeof(cnt));

        for(int i = 0;i < n;i++){
            if(izb[i]) continue;
            if(rr[i] == 1) smrt[i] = 1, Q.push(i);
            else if(a[i] == 1) cnt[i] = 1;
            else {
                cnt[i] = 0;
                for(int x : v[i])
                    cnt[i] += !izb[x];
            }
        }
        for(;!Q.empty();Q.pop()){
            int cur = Q.front();
            for(int x : r[cur]){
                if(izb[x]) continue;
                cnt[x]--;
                if(cnt[x] == 0 && !smrt[x]){
                    smrt[x] = 1;
                    Q.push(x);
                }
            }
        }
        for(int i = 0;i < n;i++){
            if(izb[i]) continue;
            if(smrt[i] == 0) spas[i] = 1, Q.push(i), cnt[i] = 0;
            else if(a[i] == 0) cnt[i] = 1;
            else {
                cnt[i] = 0;
                for(int x : v[i])
                    cnt[i] += !izb[x];
            }
        }
        for(;!Q.empty();Q.pop()){
            int cur = Q.front();
            for(int x : r[cur]){
                if(izb[x]) continue;
                cnt[x]--;
                if(cnt[x] == 0 && !spas[x]){
                    spas[x] = 1;
                    Q.push(x);
                }
            }
        }
        int cc = 0;
        for(int i = 0;i < n;i++)
            if(spas[i] && !izb[i]) cc++, izb[i] = 1;
        if(cc == 0) break;
    }
    vi sol;

    for(int i = 0;i < n;i++)
        sol.PB(!izb[i]);
    return sol;
}

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